Gravitational waves have a periodic effect on the apparent positions of stars on the sky. This effect can be quantified and hence ultra-precise astrometric measurements (like the ones from Gaia) can provide a new method to search for gravitational signals. I will describe the principles which give rise to the astrometric signature of gravitational waves, and examine this result in the context of Einsteinian and alternative polarization states. I will discuss some of the data analysis challenges that will have to be overcome when trying to search for GWs in the extremely large (>10^9 stars) Gaia data set, and will present some preliminary estimates of the sensitivity that may be achievable. I will also describe the significance of astrometric measurements for probing stochastic GW backgrounds, and derive the relevant response correlation functions for all polarization modes. Throughout, I will keep a parallel between our work and analogous results from the PTA community.