There's a video of the bot in action at http://www.flickr.com/photos/fasaxc/5944650602/.
Step 1: Parts
1 x Arduino Uno
1 x Sparkfun Ardumoto motor driver shield
1 x Sparkfun BlueSmirf Bluetooth modem
1 x 150 degree/s gyro
1 x 1.7g Accelerometer
2 x Arduino header kits
2 x screw terminals
2 x 24:1 gear motor
1 x set of 70mm wheels
2 x JST connectors
2 x LiPo batteries
1 x basic LiPo charger
3 x Multi-turn 10k potentiometers
1 x SPST switch (Radioshack)
1 x Laser-cut bamboo chassis via Ponoko (link should allow you to make one from my shared design)
1 x LED
1 x Normally-open push switch
1 x packet of Sugru to make the bumber
Assorted M2-04 machine screws (6mm - 16mm) (found on Amazon)
M2-04 nuts to match machine screws above
Assorted straight and right-angle break-away headers
Assorted jumper wires
Solid core wire
Stranded core wire
Instamorph (aka Polymorph) low-melt-point thermoplastic
Chassis: the motors didn't quite fit the mounts I made so I had to sand them down and rebuild them with instamorph. I think the sensor bundle suffers from too much vibration, it might have been better to make it more solid rather than sticking out as it does.
Accelerometer: I originally tried building the bot with only an accelerometer for tilt sensing and no gyro. It turns out that approach is a non-starter -- the accelerometer gets overwhelmed by the acceleration due to the motors so it can't be used to estimate tilt while the bot is accelerating. OTOH, using only a gyro would make the bot susceptible to drift over time so you really need both.
Gyro: I used a 150 degree/s rate gyro. From looking at the telemetry from my bot, I'm pretty sure it sometimes clip if you give the bot a knocks so if I was starting over I'd probably look for a 300 degree/s model.
Wheels: the wheels are a little fragile, after a few knocks I noticed cracks around the axle so I strengthened them with instamorph.
Motors: I also tried sparkfun's 100:1 gear motors but they weren't fast enough. The 24:1 versions have plenty of torque and speed.
Bluetooth: I use the bluetooth modem for telemetry right now but I'm also planning to use it for remote control from my Android phone. If you omit it then the robot will still work but tuning it will be harder.
Pots: I added 3 10k multi-turn pots to the design to allow me to easily tweak internal values. Using 3 might have been overkill since I tend to tweak only one thing at once.
Instamorph: Amazing stuff. It's a tough, white plastic (resembling solid nylon) at room temperature but if you heat it in boiling water it turns into a pliable goo that's really easy to work with your hands. A heat gun is great for working with it too, allowing you to melt small areas.