To summarize a few of the key points: If the abelian variety over a global field $k$ has a principal polarization coming from a $k$-rational divisor (as is the case for every elliptic curve), then the order of Sha is a square (if finite), because it carries an alternating pairing - this is what Tate proved, generalizing Cassels' result for elliptic curves. For principally polarized abelian varieties in general, the pairing satisfies the skew-symmetry condition $\langle x,y \rangle = - \langle y,x \rangle$ but not necessarily the stronger, alternating condition $\langle x,x \rangle=0$, so all one can say is that the order of Sha is either a square or twice a square (if finite). Stoll and I gave an explicit example of a genus 2 curve over $\mathbf{Q}$ whose Jacobian had Sha isomorphic to $\mathbf{Z}/2\mathbf{Z}$ unconditionally (in particular, finiteness could be proved in this example).
If the polarization on the abelian variety is not a principal polarization, then the corresponding pairing need not be even skew-symmetric, so there is no reason to expect Sha to be even within a factor of $2$ of a square. And indeed, William Stein eventually found explicit examples and published them in the 2004 paper cited by Simon.
A final remark: Ironically, my result with Stoll quantifying the failure of Sha to be a square is used by Liu-Lorenzini-Raynaud to prove that the Brauer group $\operatorname{Br}(X)$ of a surface over a finite field is a square (if finite)!