What to consider when choosing batteries for a project?
Generally, this is how I pick batteries:

Create a Power Budget


This should be the voltage, (average) current, and duty cycle required for each component of your system. For example, if you have a mobile robot that will be driving and processing, you could say 12 Volts, 1 Amp, 80% use for the motors and 5 Volts, 200 milliamp, 100% for the processor.  These numbers don't have to be exact, just in the ballpark of what you think that you will need.
Once you have a list of your power draws, figure out what the total energy each component will use.  Find this by multiplying Voltage * Current * Duty, then units will be Watt-Hours.
For the components not at battery voltage (behind a regulator), factor in the energy lost from converting voltages.  Depending on your DC-DC converter, this can be anywhere from 5% - 80% loss (moral of the story, use switching regulators, not linear).
At this point, I usually fudge a bit and add a 20% margin of error to my average power use.  I then figure out how long I want the system to run on average.  Multiply your average current at battery voltage by the amount of time that you want the system to run. You can then compare this number to the Amp-Hours available on the batteries that you are looking at


Remember to oversize your batteries a bit, as the Amp-Hour rating is determined by C/20 in most cases. C being the rated current (a 3.3Ah pack has a C of 3.3 Amps, but tested at 165 milliamp).  Picking batteries is not an exact science in most cases, and it may take a few tries to get right.

Choosing Battery Chemistry

As far as picking chemistry, it depends on the project.  Weight, size, and cost factor in heavily along with the run time for your system load.

A few questions to ask about your need:


Budget
Size and Weight Constraints
Project Lifespan (Charge cycles)
Charger cost, maintenance


A few choices:


Lead Acid, high cycle count, very reliable, easy to charge, yet they are large and heavy for the capacity.
NiMH and NiCd, go-to hobby batteries, average size and energy density
LiIon and LiPo, super-light, more expensive, high energy density, can be unstable if treated improperly.  Good for high-current discharge (20*C and higher).
LiFePo, high cycle count, about the same energy density as LiPo.


Brief Example

The attached example is for an autonomous lawnmower project that I worked on.  We began by listing all of the components required at each voltage.  In the end, we choose to run two different battery stacks to help eliminate some of the noise from the high-current devices.

The 12V battery stack also provided power for the 5V electronics, which we ran through a 80% efficient DC-DC converter.  You can see the additional 20% factor in the spreadsheet.

In the end, budget was the main constraint, with size and weight not constraints for the project (300 pound lawnmower, what's a couple batteries?).  We ended up using a 64Ah 24V lead-acid stack and a 17Ah 12V stack.  Our run times reflected what is in the sheet.

In practice, the 24 Volt battery stack lasted much longer, as we used current figures that were close to worst case (100% full speed forward and cutters in thick grass).  As a result, on the next iteration, we combined the 24V and 12V stacks together.