In principle you have to go for LiPo batteries. For the AX/MX motors you need the ones that are called “3S” meaning they have 3 cells in series. With the nominal voltage of a LiPo cell of 3.7V the 3S batteries will provide 11.1V. In reality the voltage starts at about 4.2V/cell when fully loaded and is not recommended to let it go bellow 3.3 - 3.4 V. You should be fine with them.
One of the important features of the LiPo batteries is that they can provide very high discharge currents. That is indicated in the “C” characteristic of the battery. That shows how much multiply of the battery capacity (in mA) can deliver. For instance a be terry that is 2200mAh and has a 25C rating (pretty standard) will be able to give you sustained current of…(be prepared) 55A, albeit only for a few minutes (2.4 to be more exact = 60/25). Of course if you use the battery at 5A you will get 10 times more time.
The only thing left is to choose the shape, dimension and the capacity based on the limitations you have for the robot (where you want to place them etc.). Keep in mind that they add weight to the robot (not that little) and the higher you place them the more you will stress the lower part of the body. Have look on Hobbyking website to have an idea what you have on offer - you will be surprisingly overwhelmed.
The design that I have for my robot uses 2 batteries (I use 2S batteries as the robot uses XL-320 servos) right down in the soles:
And here you can see how the battery fits in.
It simply slides from the back and it fits snugly between several walls.
This way the impact on servos is minimal (only when you need to lift the foot up there is some impact) and as an added bonus the heavier soles increase significantly the stability of the robot.
To inject the power I use some small boards that are on the inside of the shins. They act as unidirectional current gates (not allowing current to flow into the battery when is discharged for instance and another battery is inserted in the other leg):
The two pins that are on the back are where the battery connector is going in.
And this is a picture of an earlier version (smaller batteries and feet without the added DOF for ankles) where you can see how all things come together:
A very important benefit of this is that you can swap the battery one by one when they are low, without the need to shutdown and restart the computer on the robot (which is a big hassle). The hot swap models above ensure that once a new battery is inserted the current doesn’t “rush” in the remaining battery.