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!
Incorrect Path
I'm curious as to what does the moon's orbit around the sun looks like?
One might think the orbit (in the sun's rest frame) follows the path of an epitrochoid.
A (very) over exaggerated view of this motion (for unrealistic parameters, thus, not an accurate representation) can be seen in the following animation:
Note that if you change the ratio of the different radii to values that are to scale, then the plot would look more like an epicycloid as in the following example animation. The orbit is more realistic but still exaggerated because it would be impossible to show half an orbit to scale.
The correct result is shown in the zoomed-in view of David Hammen's post above.
Update/Correction
The above animations are flawed because the little red dot orbits as fast as the blue circle rotates as it "rolls" around the large red circle with no slippage. For a realistic Earth-moon system, there should be a lag between the rotation of the blue circle and the red dot, as if the blue circle were "slipping." Or equivalently, one would not use a rigid axis connecting the center of the blue circle and the red dot. This would result in there never being a negative velocity of the moon relative to the sun in the fashion shown by the epicycloid path in the 2nd animation above.
Incorrect (still exaggerated) Path
The correct path uses two different orbit rates, one for the Earth about the sun (i.e., 1 year) and one for the Moon about the Earth (i.e., ~27 days). In the following example, which is still an incorrect (i.e., exaggerated) orbital motion but much better approximation, I exaggerated the ratio of the astronomical unit to Earth radius by a factor of 100 and increased the moon's orbit by a factor of four to help make the visualization more obvious.
Correct Path
The following example does not exaggerate the orbital periods relative to each other and is a zoom-in of the above graphic (oddly the GIF, created through the same methods, does not loop on my screen). Here the orbit is always convex with respect to the sun, as David has correctly stated.
Best Answer
It's good old Newtonian gravity! The plane of the galaxy can be approximated as a disk made up of stars and gas, with a density $\rho(|z|)$, that decreases with absolute distance $|z|$ from the plane.
If you were to assume that the Sun was close enough to $z=0$ and that the radial variation in $\rho$ was negligible enough to treat the disk as an infinite plane (this is not bad, the amplitude of the Sun's motion is only about 10% of the radial scale length of the disk density), then you could construct a little cylinder through the plane, with one face at $z=0$, where $g=0$, and use Gauss's law for gravity to estimate the gravitational acceleration at height $z$. $$ g(z) \simeq -4\pi G \int_0^{z} \rho(z)\ dz$$
Now $\rho(z)$ approximates to an exponentially decaying function with a scale height of maybe 200-300 pc. If we are closer to $z=0$ than that, then the density can be roughly said to be a constant $\rho_0$. Putting this into the equation above, we see that $$g(z) =-4\pi G\rho_0 z.$$ But this is simple harmonic motion with an angular frequency $\sqrt{4\pi G\rho_0}$.
The density of the disk near the Sun is estimated to be 0.076 solar mass per cubic parsec (Creze et al. 1998). Using this value, we get an approximate predicted oscillation period up and down through the disk plane of 95 million years.
Note added: The previous paragraph is the reverse of what is actually done - the dynamics of stars in the solar vicinity are used to estimate the density in the plane. However, just counting up stars and estimating the contribution of gas does give a similar result - and in the process, illustrates that the contribution of dark matter to the density of the disk is very small.