The Gaia mission offers a new opportunity to search for the low-frequency gravitational wave background using astrometric measurements. In this paper, the astrometric effect of gravitational waves is reviewed, with a particular focus on the effect of non-Einsteinian gravitational wave polarizations. A stochastic gravitational wave background generates a correlated vector field of astrometric deflections on the sky. A convenient decomposition for the correlation matrix is introduced, enabling it to be calculated for all possible gravitational wave polarizations and compared to the redshift correlations from the pulsar-timing literature; in the case of a general relativity background of transverse traceless gravitational waves, this also allows us to identify an astrometric analog of the famous Hellings-Downs curve. Finally, the cross correlation between the redshift and astrometric signal is also calculated; this may form the basis for future joint pulsar-timing and astrometry searches for arbitrarily polarized gravitational wave backgrounds.