Step 1: Parts List
1 x Arduino (preferably UNO)
1 x ATmega328 chip (other versions work too, more on this later. You'll most likely want one with a preloaded bootloader)
1 x 28 pin DIP socket (holds the ATMega, not absolutely necessary but you really should have it)
1 x 5v Regulator (L7805)
2 x 10 uf Capacitors
1 x 16Mhz Ceramic Resonator (a 16Mhz crystal works too, but you will need additional capacitors which take up space.
1 x pcb board (got a small one that fit in an altoid tin from radioshack for a few bucks)
1 x breadboard (to test the circuit)
2 x motors (I used pager motors with planetary gear boxes from robotshop.com)
2 x wheels (also got these from robotshop.com, but you can use whatever works)
1 x L293D (motor driver chip, which is necessary if you will be using motors)
1 x pushbutton (my code revolved around this thing, definitely useful)
Wires! Will need a lot to breadboard and solder.
Coin cell batteries (these keep the size small enough to fit in the altoids tin)
2 x photoresistors (lots of fun programs you can write for these)
2 x RGB LED's (gives it the personality!)
1 x mic element (lets it listen and react to sound)
Anything you think would be cool! I wanted to add sound, but sadly didn't have enough space left for a tiny piezo speaker.
Tools: clippers, soldering iron, perhaps a friend to help hold wires