I would avoid using two batteries! Try going for a 8.4v battery. I would probably get one around 2000mAh depending on how long you want your robot to run.
You can connect the battery right into your servos, then into the voltage regulator on your Arduino, and for your motors you can use a 6v UBEC.http://www.hobbyking.com/hobbyking/store/__17158__6V_3A_UBEC_2_5S_Lipoly_6_23v_.htmlhttp://www.robotmarketplace.com/products/batteries_main.html
Best of luck!
EDIT: As for how do you pick a power source, I generally find the highest voltage component that i'm using and buy a battery for that. Then I regulate the voltage down for my other components. When It comes to selecting the amperage you need to add up how much power your robot will suck, then find out how long you want your robot to run.
For example say your robot sucks 1 Amp and you need it to run for .5 hour. You would technically need 5000mAh battery, however, its good practice to buy a battery with a little more mAh then you need!