A servo is different than a motor.http://www.societyofrobots.com/actuators_servos.shtmlhttp://www.societyofrobots.com/actuators_dcmotors.shtml
Just make sure you know the difference. I personally perfer servos just because control is a lot easier. The motors you selected will work fine though.
If you are going to use two motors, I assume you are using differential steering. What you would want is not 4 wheels, but two wheels and a castor. This is my very 2nd robot:http://www.societyofrobots.com/images/materials_HDPEexample.JPG
The wheel on the far right is just an idle wheel used for furniture. If you used a fixed wheel, it would drag across the ground resisting your robot from turning. Just search the web for castors, there are many many types. You could however, by using a chain, link the front and back wheels together, almost like a tank but without treads. One motor would drive both wheels on a side. It would still be differential drive. I have done that before and it works really well for rough terrain, but as a tradeoff turning requires more energy.
As for batteries, a single lithium ion battery would be 3x better and still cheaper than the battery you chose:http://www.onlybatterypacks.com/showitem.asp?ItemID=10920.23http://www.onlybatterypacks.com/showitem.asp?ItemID=10978.23
Voltage and mAh are key. I personally recommend the 2nd battery . . .
You also need a battery charger. Search that site to check out the chargers.
The lithium battery chargers are generally more expensive tho. I think in the next few years lithium ion will be the best battery to use, so probably not a bad idea to just start using them.
Or for a litium ion charger you can do this instead:
"An adjustable power supply that current limits likehttp://www.mpja.com/productview.asp?product=9303+PS
works just as well. You
set the voltage limit to 4.2v * number of cells, then set the current limit to the cell capacity (1.4a for your cells) it will constant current charge until it reaches 4.2v/cell then constant voltage charge until its full, which is when the battery capacity has dropped to zero. Thats the recommended charge profile for lithium and lead acid batteries anyway." (quote from my friend, I havnt tried it yet)
For your microcontroller, you will need a programming board. Basically a way to hook it up to your computer to be programmed. Paralax should offer one. Just look around, it will be obvious when you see it.
You also need a bread board or protoboard to stick your wires in.
Being your first robot, I wish you luck. I totally failed on my first attempt
Whatever you understand the easiest, do. Simplicity is best.