Sources of robot hardware:

SolarBotics - Cheap GM8/9 motors are excellent for smaller robots. Also carries wheel watcher modules for the GM8/9.
Trossen Robotics - All sorts of parts. Sells Arduino.
Sparkfun - all sorts of fun stuff.
Acroname - a good source for sensors.
Lynxmotion - awesome parts for bots, especially larger ones.
Pololu - Home of the 3Pi robot.
Budget Robotics - very inexpensive robot materials and kits. Unfortunately, all of their kits use continuous rotation servos.
Interstate Plastics - sells EPVC in large sizes.

Resources for Arduino:

Arduino.cc - The website for Arduino.

Forums and good sources of info:

Robots.net - good news, an interesting gallery.
Seattle Robotics - good information for WinAVR beginners.
Trossen Robotics Forums - Very popular forums.