Here is a quick example of what you can do with Lego Mindstorms NXT and a HiTechnic Gyro Sensor.
This is a proportional controller that provides orientation control, built with the NXT graphical programming language.
The PID controller implementation, which is not shown, required 4-5 screens worth of blocks and works surprisingly well.
Here is the video of the controller in action.
Another bit of interesting news is that ROS now has support for the Lego Mindstorms NXT. Now, the next step is to build one of these gyro cars and test out the NXT python interface with ROS.