To choose a battery, you must know how much voltage you need, how much current you will be drawing from it, and what physical attributes you require from the battery (size, shape, weight, terminal type). Then you can compare options based on price and performance.
Choosing batteries for the MCU:
This robot's servos require 4.8 to 6V, and it's MCU requires 7 to 12V. Also, there is a certain level of separation that is needed between the two voltage sources. If the servos and MCU were powered directly from the same voltage source, it might cause the Arduino to reset while the servos pull current. This can be handled with voltage regulation, but I chose to use a separate 9V alkaline battery for the Arduino. The MCU is only going to pull maybe 100mA, and it needs a higher voltage than the servos. The two vastly different requirements called for two different batteries. 9V Alkaline batteries are readily available and weight about 46.39g (as measured). Compare this to eight servos at 38.52g each, or four NiMH AA batteries at 27.76g each (Note: the 9V pictured is a Rayovac battery, but after researching batteries it is advisable to avoid Rayovac for their dishonest specifications).
Choosing batteries for the servos:
Servos can pull a substantial amount of current, especially when eight of them are running at once. Each servo can pull around 250mA, so eight servos could pull 2A from the batteries. This is a serious amount of current so choosing batteries carefully becomes important.
The combination of a need for high current and low weight means that the batteries will drain quickly. This makes rechargeable batteries a requirement and rules out the inexpensive alkaline types. Common rechargeable batteries in robotics are NiMH, NiCd, LiPo, and Li Ion. Lithium batteries are expensive and require the additional cost of a charger. Unfortunately, lithium batteries are vary light weight and can handle high current draw, so they would have been a perfect choice if they weren't so expensive. If you have access to lithium batteries, and know what you're doing, you should use them.
Between NiMH and NiCd, NiMH is arguably better. They are similar, but NiMH is said to suffer from less memory effects. Unfortunately, nickel is a heavy element. This is a necessary evil because nickel batteries are otherwise ideal. They have extremely low internal resistance (good for high current applications), a fairly flat discharge curve, plus NiMH chargers are common and inexpensive. The use of nickel batteries over lithium also means that standard sizes like AAA, AA, and C batteries are a possibility. This makes mounting the batteries cheaper and easier. AA sized batteries best fit the weight and battery life requirements.
Example of an Alkaline AA: http://data.energizer.com/PDFs/E91.pdf
Note the very poor performance under high current, the poor discharge curve, and the explicit warning against high current appliances such as digital cameras.
Example of NiMH AA: http://data.energizer.com/PDFs/nh15-2300.pdf
Note that at 2300mA, the battery allegedly lasts for an hour. Also note the flat discharge curve compared to the alkaline battery.