HMC5843 - I think this one might be the best, if somebody knows how to do surface mount. It does 3-axis magnetometry which should avoid the requirement that the chip be parallel to the plane of the earth (I think it also uses an accelerometer in this process). Communicates via I2C. $20 at digikey.
Lots of information about it here (looks like no accelerometer). That it needs a resistor and two capacitors might bring the real final the price up.
Glitzo demo video: http://www.youtube.com/watch?v=T85Af1o_YAs&feature=channel_page
The one Skory has is the Hitachi HM55B. $30 at Parallax Big pro: already mounted. Big con: only 2-axis. Medium con (maybe): not I2C, but, the code to read it with an Arduino is straight-forward and already exists.
Mar 16 2009 by Lamont Lucas: I ordered the Honeywell HMC1052L breakout board and sensor from sparkfun. (with board, $15, just the leadless 14 pin QFN package chip is $9). It should be in my hot little hands by thursday so I hope to have it working by sunday. It's a neat two-axis sensor, and the output is two analog voltages for
Mar 16 2009 by Mikolaj Habryn: That looks like an ideal choice - might well be pin compatible with existing breakout boards from sparkfun for the 2-axis ones, too. Soldering LCCs might be a problem, though - simple SMD isn't too bad, but with these, there's no way to inspect the joints. I guess we can try it and see - I think I've tried to do one of these with a hot air