I think I am going to purchase this motor: http://www.sparkfun.com/products/9347. If I use two of these:http://www.sparkfun.com/products/341 to power it how could I keep the voltage at 6 volts?
You're putting the cart before the horse.
For one thing, do you even know how much current one of those servos needs (running vs. stalled, as well), vs the mAh of the battery? If you don't understand this question, you'll probably end up with a robot that moves for about 5 minutes, then needs recharging.
In order to get 6 volts from a pair of those batteries, you would need some kind of voltage regulation scheme. In a pinch, a 7806 voltage regulator will do this, but you don't get much in the way of current output (about 1 amp - with a good heatsink); the 78xx family of regulators also aren't very efficient (and with such low battery mAh, you need as much efficiency as possible to extend your runtime). So now you're looking at a low voltage switching regulator (I know they make a 7805 equivalent form of these - so maybe a 7806 equiv also exists) - or building a buck converter, or something else.
Also - do you have a charger for those batteries - you can't just plug one of those up to anything to charge it (not unless you want a nice fire).
You'd be better off powering the servos from an 4-cell AA battery pack, running alkalines (for 6 volts) or NiMH (for 4.8 volts - or, if you can set up a 5-cell pack, you'll get 6 volts). This will give you the voltage you need, plus a greater mAh rating for longer run-time. You won't have to deal with voltage regulators, either. Run the Arduino off another pack separately...