The first example of an abelian variety with nonsquare Sha was discovered in a computation by Michael Stoll in 1996. He emailed it to me and Ed Schaefer, because his calculation depended on a paper that Ed and I had written. At first none of us believed that it was what it was: instead we thought it must be due to either an error in Stoll's calculations or an error in the Poonen-Schaefer paper. Stoll and I worked together over the next few weeks to develop a theory that explained the phenomenon, and this led to the paper http://math.mit.edu/~poonen/papers/sha.ps - that paper contains a detailed answer to your question.

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)!