Arduino & Motors on Battery Power

I'm planning on getting 2 servos and a dc motor, but I'm having trouble figuring out how to power them by battery. I was thinking that I would go with Nickel-cadmium batteries since I will likely be doing deep cycling, but I can't seem to find any in capacities over 1Ah. If I'm hoping for around 2 hours of continuous use, what would you recommenced to power them?

NiCd is very obsolete. NiMH is cheaper, has several times the capacity for a given size/weight, and is better for the environment.