Servos operate at about 5 to 6 volts, so you can connect the two batteries in series to form a 7.4v battery, and use a regulator to step down the voltage to between 5 and 5.5 volts. You will want to use a switching regulator (or something similar - just not a linear regulator as this will overheat). I've used the 3 amp model of this regulator with success: http://www.dimensionengineering.com/DE-SWADJ.htm. Fairly small, pretty cheap. You shouldn't need a heat sink.
Batteries in series will increase the voltage, and in parallel it will increase the number of amp-hours. You didn't say how much current each servo will be pulling, so you might need a bigger (as in higher amp-hour rating) battery. Take a look at this one: http://www.sparkfun.com/products/10471
After being stepped down by the regulator, this 5 to 5.5 volt output can be safely connected to the microcontroller to power it.
As for additional components, I'm no expert but I think you will need a crystal to drive the clock, decoupling capacitors to smooth the power (switching regulators are noisy), and probably a few other passives. I'm assuming you don't need Arduino-style programming functionality (i.e. USB programming), so you will need to buy an AVR programmer.