All batteries have an amp-hour rating that says how much charge is in the battery. A triple A baterry and a D cell battery are both 1.5V batteries, but the D cell has a much higher amp-hour rating than a triple A.
You could use the amp-hour rating directly, but what I find more useful is to get a watt-hour rating. This is more useful as robotic applications tend to use battery packs of various voltage ratings in combination with a voltage regulator.
A battery has a nominal voltage; get the watt-hour rating by multiplying the amp-hour rating by the nominal voltage. Now you can divide this watt-hour rating by the power draw of the robot (in watts) to get the number of hours the battery can power the robot.
You can also use this to estimate run time by power ratings for each component before you ever actually build the robot; four 250mW motors total for 1W of power draw. Assuming the Arduino controlling it draws 50mA at 3v3, the controller draws 165mA. This gives a total power draw of 1.165W (again, estimated).
Now, a 1000mAh, 7.2V LiPO battery back has (1Ah x 7.2V) = 7.2Wh of capacity. This means that it will run the example circuit for (7.2Wh / 1.165W) = 6.2 hours = 6 hours and 12 minutes. Again, this is an estimate, which may be more or less depending on whether you run the motors at full capacity for the whole time and the efficiency losses in the voltage regulator and other equipment, but it should be generally correct.
Regarding your bonus points, the other devices you've listed aren't power storage devices. They can run indefinitely, provided they're powered. A solar cell doesn't hold a charge, so it can't run anything for any amount of time if there's no sun. If there is sun, it can supply its rated power as long as the sun is out. Note again though rated power - you can't run a 5W robot on a 1W solar cell. Same applies for all other power supplies. The are power supplies, not power reserves like a battery.
