Something like the following: http://www.robotshop.com/magnetic-sensors-compass.html
The advantage over a gyro would be that you can always tell what direction the robot is facing, even after significant interference like shaking which can confuse the gyro.
It would also be much easier to program for.
+1 (10char)
Hmm…
I used a compass on a robot for another competition, but it had a problem when used around metal… I think that the metal perimeter, the metal robots, and sometimes metal field elements would be a large noise generator for the compass.
How bad was the interference?
It depends… on one side of the room I was working in, there was a bunch of metal equipment for a electronics class. The interference was enough that on the side of the 8’ by 8’ field that was closest to the metal (about 3-4 ft away), my control loop would cause the robot to turn towards the metal, even though the robot should have traveled straight.
I don’t have a numeric answer, though. I’m going to do some more experimentation with the compass I have, though, and see how bad of a problem it really is (quantitatively).
We’ve used digital compasses before, with mixed results. Our room is particularly bad for this sort of thing, I remember one test we did resulted in drunk robots meandering as they pleased. However, If you isolate the compass from the motors, the compass can be calibrated. Eventually, we ended up with this test. It wasn’t perfect and I don’t know if it could be reliable enough for competition use, but it showed some promise.
Matt
Magnetometers are a novel concept but require just as much work if not more then a gyroscope unfortunately. In addition they do get quite temperamental around motors. 
We used compass sensor for our robocup competitions.
The main issue is always the resolution and the accuracy. Even if the accuracy is up to +/- 2 degree, but if you extrapolate the path down, it is still quite a significant amount of error.
Of course, you can use it with PID programming to solve this issue. But it is definitely not a walk-in-the-park solution.