I am working on my first robot project. It would be a simple differential drive robot, plus two photoresistor to avoid dark or light.
I choose to use Arduino as the controller, and two modified Hitec continues rotary servo to drive the wheel. I believe I will keep on other robot projects after this (like a bigger ones with more functions, and I will try DC motors, too), and I hope my investment now could also be used later.
For the Arduino, I believe it's better to use a power from 7V to 12V; while the best for the servo is 6v; and of course, it's also better to use two powers, one for the controllers, and one for motor/servos.
I will use a 9V battery (like this one: Nine-volt battery - Wikipedia) for the controller, I didn't find a rechargable one yet (how do I recharge this kind of battery??).
I am still not sure what to use for the servos. One option is to buy a battery pack (like this one: RobotShop | Robot Store | Robots | Robot Parts | Robot Kits | Robot Toys), then I will have to buy a charger for it, too, and they don't have any stock in RobotShop.ca (I am in Canada), I checked local The Source (the store in Canada, just like Radio Shack) and they don't have it either. I thought about battery holders (like this one:RobotShop | Robot Store | Robots | Robot Parts | Robot Kits | Robot Toys), but I can only find those to hold either 4 or 8, which would be either 4.8V or 9.6V. I also found this battery pack (http://www.liquidware.com/shop/show/BP/Lithium+Backpack+Stealth), it's quite impressive (especially the fact that I can recharge it using USB), while the price is quite impressive, too, cause I have to pay about $20 dollars to ship it to Canada (and don't know how much I have to pay for the custom yet).
A 9V PP3 type battry will not power your robot for long, they are very low capacity.
My recommendation is to go with a 6v ni-mh battery pack and use an external low dropout regulator to provide 5v power for the arduino.
I have used the LF50CV regulator for an application like yours. This provides up to 500ma for anything powered from the arduino 5v supply. The servo motors can be powered directly from the battery and the system should be ok down to just below 5.5 volts
If you are only powering the arduino chip with no shields or other components being powered, you could also you an LP2954 or L4931 250ma low dropout regulator if those are easier to obtain.
If you are looking to minimize the cost of yr project, you may want to consider using 5 standard rechargeable AA NI-MH batteries plugged into a battery holder. You can use two of the 4 cell holders in yr link, cut one down so it holds a single cell. (You can also make a battery pack by soldering to the batteries but this is tricky to do because its easy to overheat and damage the cells so not reccomended.)
I've decided to go with 5 NiMH rechargeable batteries with battery holders (I will buy a 4-cell and a 1-cell and connect them together).
I did some reading on the LF50CV, as well as MC33269D-5.0 which is the regulator on the Arduino Duemilanove board. The LF50CV has a drop-out of about .5V while the MC33269D-5.0's drop-out is about 1.0V.
So, I am thinking: can I just replace the on-board MC33269D-5.0 with a LF50CV?
I think mem's suggestion is to use the regulator to supply 5V to the Duemilanove using the "5V" pin as the power input.
This way you keep the regulator on the Duemilanove and just bypass it with thelow dropout regulator. No need to yank it unless you want to dedicate the Duemilanove to the task.
Replacing a surface mount regulator is possible but difficult to do without the proper equipment. Take care not to overheat the board if you are not experienced with SMT.
Before unsoldering the regulator, try it with your 6 volt battery. The actual dropout of the regulator is dependant on current and the regulator may work with your Arduino board below 6 volts. Si I would see if there is enough run-time using the existing regulator
Looking forward to reading about the project when its done.