You should take a look at Breadboard Arduino Compatible Parts Kit Retail - RTL-10422 - SparkFun Electronics for how to build a breadboard arduino. Look at the links halfway down the page for directions for assembly. There is also a printable overlay to put on your breadboard to make assembly very easy. You don't have to order the kit, use your own components if you have them.
I use this to make a "sacrificial" arduino for testing where the unit may be damaged or lost. Worst case, I'm out $12, but I have a fully functional and programmable arduino.
In addition to what CrossRoads mentioned, you'll need an FTDI breakout or cable for programming. I tried the remove/program/reinstall route. It isn't convenient and you end up breaking chip leads. Buy the FTDI programmer and make the breadboard programmable. The FTDI is $15 or $10 if you buy the female adapter separate and solder it on (SparkFun FTDI Basic Breakout - 3.3V - DEV-09873 - SparkFun Electronics and FTDI Basic Breakout - 3.3V - DEV-10009 - SparkFun Electronics). You'll also need a few inches of 26 gauge hookup wire or use your breadboard jumpers if they aren't too long.