You're looking at three main bits to get the whole thing up and running:
- The body - motors, gears, etc
- The electronics - basic concepts, sensors, motor drivers, and if you get into more complex stuff, computerish things like microcontrollers
- The software - basic AI
(obviously there's some overlap here)
If you have limited experience with these things, a kit from somewhere like Lego or Fischertechnik is an excellent place to start. These will take care of the hard stuff, letting you get straight in. Its also a good way to test the waters - see if you really want to get into robotics (it can become addictive and expensive very quickly).
If you want to do it yourself, I recommend these books by David Cook:
See also http://www.robotroom.com/
I tend not to get into the body building much, preferring off-the-shelf stuff. Basic Lego Technic sets have served me well, and I'm currently using Tamiya gearboxes and bases. I'm far more interested in the computer side, building small microcontroller-based computers and writing the software from scratch.