Andromeda/Milky Way collision: How, and how accurately, can a galaxy's lateral velocity be measured?
That's a really good question. You're right that measuring the tranverse velocity is a very difficult measurement, mostly due to Andromeda's distance from the Sun. The problem can be tackled in two ways: directly, and indirectly.
Direct measurements mean actually tracking a positional change between Andromeda and even more distant objects assumed to be essentially at rest, like quasars. The recent discovery of water masers mentioned above should make this possible; a transverse velocity of ~100 km/s is an angular shift on the order of 10 microarcseconds per year. This is much smaller than is possible with optical telescopes; the extreme baselines of radio telescopes like the Very Long Baseline Array, however, do make direct measurements feasible. These observations are currently taking place, and we should have a published measurement within a couple of years.
Indirect measurements of Andromeda's transverse velocity use a few different techniques. The Loeb et al. (2005) paper made their estimate based on the fact that M33, a neighboring galaxy to Andromeda, shows no sign that its stellar population has been disturbed by passing nearby Andromeda. This constrains the possible range of directions and speeds of Andromeda's velocity. They combine this with data on M33's orbit, plus simulations of how close the galaxies would have to be to show an effect, and estimate both a direction (mostly eastward) and speed ($100 \pm 20$ km/s) of Andromeda's proper motion.
A second indirect method was published by van der Marel & Guhathakurta in 2008; they used information on the orbits of satellite galaxies orbiting M31 to estimate the center of mass (or barycentre) of our Local Group. Since the position and velocity of the Local Group barycentre depend partially on M31's orbit, they also estimated a transverse velocity. Their result is -78 km/s W, -38 km/s N.
The upcoming direct measurement of M31's proper motion should answer which (if either) of these other estimates are correct. In addition, we're looking forward to answering several interesting questions regarding both the past and future of our Local Group of galaxies. Stay tuned!
There's new information on this, just released today (Thu 2012-05-31).
According to this study, based on Hubble data, M31 is on course for a head-on collision with the Milky Way.
Previously, it was unknown whether the far-future encounter will be a miss, glancing blow, or head-on smashup. This depends on M31's tangential motion. Until now, astronomers have not been able to measure M31's sideways motion in the sky, despite attempts dating back more than a century. The Hubble Space Telescope team, led by van der Marel, conducted extraordinarily precise observations of the sideways motion of M31 that remove any doubt that it is destined to collide and merge with the Milky Way.
"This was accomplished by repeatedly observing select regions of the galaxy over a five- to seven-year period," said Jay Anderson of STScI.
The collision will start in about 4 billion years. After an additional 2 billion years, the two galaxies are expected to merge into a single elliptical galaxy.
It is likely the Sun will be flung into a new region of our galaxy, but our Earth and solar system are in no danger of being destroyed.
Phil Plait, the "Bad Astronomer", discusses the findings here, and this article has more information (including that the Triangulum galaxy M33 will likely take part in the festivities, and might even hit the Milky Way before M31 does).
It should be an impressive show, but don't start stocking up on popcorn just yet.
The cool thing about this is that we're now able to measure lateral motion of stars in another galaxy. (The really cool thing about this is, hey, colliding galaxies!)
It has not yet been measured, but there is an ongoing effort to make proper motion measurements using water masers in Andromeda (Water Masers in the Andromeda Galaxy: The First Step Toward Proper Motion). Since masers are very compact, and interferometric observations at radio wavelengths can measure precise positions, the author suggests that it will be possible to measure the proper motion of Andromeda in the next couple of years.