12V vs 24V came down to availability for me. In general I noticed that most motor controllers could handle up to 24V. In general it seemed that price was correlated with amp draw, so it made sense to try and use 24V motors because that would mean half the price for the same power (for the controller). However, once I figured out what I actually needed in terms of power and gearing, I started searching for motors and found that what was available was 12V motors. The 24V gear motors available were generally much more power than I needed.
So Soeren has it right. Either way I had to start with figuring out how much power I needed, which came down to brushing up on physics.
I chose a Li-Poly battery on ebay for about twice the price of a sealed lead acid equivalent and 1/5th the weight. That's right, 1/5th. That could dramatically change the weight of your robot.
Edit: And possibly explode!