The Arduino is a fine way to get started. There are tons of tutorials on the web, and lots of pluggable "shields" that make it easier to add things like motor controllers, sensors, communications, etc.
An option to the Arduino might be the Raspberry Pi, which is also aimed at fairly beginning programmers. It has more power, and allows you to plug in many USB devices like webcams, but it doesn't have as many tutorials or add-on hardware devices as the Arduino.
Specifically for robotics, there's also the Axon set of microcontrollers from this site, and the Arbotix board (which is Arduino-like) for driving Dynamixel servos.
Personally, I like stripboard, or soldered breadboards. This allows me to prototype circuits in a fixed substrate, without having to wait for real PCBs to be built. Once I know what I want to do, I design PCBs in a software program and have my own custom circuit boards made, which can be done for $5 per square inch of board at oshpark.com.