Suppose that $k$ is a finite field with $q$ elements. Let $C_i$, $i = 1, 2$
be two smooth projective geometrically irreducible curves over $k$. Set $X = C_1 \times_{\text{Spec}(k)} C_2$. In principle we know how to compute the Brauer group of $X$ in terms of the action of Frobenii on the \'etale cohomology of $C_1$ and $C_2$.
Let's assume there is no nontrivial isogeny from the Jacobian of $C_1$ to the Jacobian of $C_2$, or equivalently that the characteristic polynomials $P_1, P_2$ of the Frobenius endomorphisms of these Jacobians are relatively prime. This means that the Picard group of $X$ is generated by pullbacks of invertible sheaves from $C_1$ and $C_2$. Thus for $n$ prime to $q$ the exact sequence
$$
\text{Pic}(X) \to H^2_{\acute{e}t}(C_1 \times C_2, \mu_n) \to Br(X)[n] \to 0
$$
coming from the Kummer sequence and cohomology
is (in principle) computable. Working through what is known about \'etale cohomology of curves over finite fields you'll get
$$
\left(
H^1_{\acute{e}t}(C_{1, \overline{k}}, \mathbf{Z}/n\mathbf{Z}) \otimes
H^1_{\acute{e}t}(C_{2, \overline{k}}, \mathbf{Z}/n\mathbf{Z}) \otimes \mu_n
\right)^{\text{Gal}(\overline{k}/k)}
$$
for the $n$ torsion in the Brauer group of $X$.
If there are nonzero isogenies between the Jacobians, then you'll just get a quotient of this.
If $n$ is not coprime to $q$, then you'll have to look at papers of Milne to see what happens.
Now it is clear that you can certainly get lot's of Brauer classes. In fact, you can show from the above that if $P_1$ and $P_2$ have a factor in common modulo $\ell$, then there'll be an $\ell$-torsion class in $Br(X)$ for $\ell$ a prime not dividing $q$. And given a situation as above and an $\ell$, you can always find a finite extension $k'$ of $k$ such that this thing happens over $k'$. Enjoy!