To properly answer this, you first have to determine how long you want your application to be able to run on a full charge. Clearly, it'll run on a 9V battery, but not for very long.
To determine the appropriate power supply, you need to calculate the overall voltage and current requirements for the various components.
The Mega needs a pretty minimal power supply, just 5V @ 200mA.
You don't specify the ratings for your motors. Servos are typically 5-6V @ 500mA, but I'm only guessing. Steppers and DC motors vary quite a lot.
The first step would be to find the specifications for all your motors, and find the maximum values, specifically the operating voltage and stall current. Hypothetically, say the maximum voltage for all the motors is 5V, and the stall currents for the steppers, servos and DC motors are 1A, 1A, 500mA, 500mA, 3A, and 3A respectfully. (Again, this is just an example. Find the true values yourself). That means you'll need a supply that can safely deliver 1+1+0.5+0.5+3+3+0.1 = 9.1A @ 5V or 45.5 watts.
If you want to use a battery (instead of a stationary supply like a DC adapter), you'll need to chose a battery with adequate mAh rating, which is the total number of amps it can deliver in 1 hour.
Perfectly predicting battery life greatly depends on the battery chemistry and your application's average current draw, both of which great very complicated, so I won't go into that here. A battery is considered effectively "dead" when it's depleted to around 80% of it's fully charged voltage. You can lookup the formulas and do the math yourself, or you can use some online calculators to help you estimate discharge times for different battery and load configurations.
However, as a general rule of thumb, you want to select a battery with a voltage greater than the minimum voltage required by any of your components. For your application to run for 1 hour, it's mAh rating should also be greater than your application's total current consumption. To run longer, you'll need to find a battery with a higher mAh rating, or higher voltage that a switching regulator can use to convert that extra voltage into current.
The other important factor, which complicates these calculations, is the type of voltage regulators you use. If you want to power everything from a single battery, you'll definitely need some voltage regulators. Preferably, you should use high-efficiency switching regulators. For this purpose, you can find cheap UBECs used for RC applications on Amazon or Ebay. You should have one for the Arduino and each motor (or pair of motors if you want to save on cost or complexity). Just make sure the regulator's voltage and current requirements are greater than what's consumed by your components.
I find using 2 or 3 Lipo batteries in series, especially 18650 cells, are the cheapest and easiest way to provide power for mobile applications that have high spikes due to motors. For stationary applications, a 12V DC wall adapter with a high current rating would be simpler.
If you want to use akalines, I'd recommend using separate batteries for the Arduino and motors. Akalines aren't well known for being able to deliver high current. Motors can demand a lot of current, and if the battery can't deliver enough, it'll cause the voltage to drop, resulting in the Arduino browning-out. However, lipo batteries, or non-rechargeable lithium batteries are better suited for this.