Disposable AA batteries
pros: produce higher voltage than rechargeables when new and fully charged; sold everywhere.
cons: very expensive over the long run; not earth-friendly (disposable batteries are classified as toxic waste in most localities)

Rechargeable batteries
LEGO lithium ion battery pack
pros: high energy density (will deliver useable power for a longer time than other kinds of batteries)
cons: more expensive than NIMH cells; makes the NXT brick thicker requiring adjustments in robot construction;

Usage tip: If the battery is charged and doesn't seem to be working, make sure the contacts are clean and making contact!

NIMH AA cells
Standard cells
pros: lowest cost over the long run; readily available from many different retailers.
cons: constant and fairly rapid charge drain when not in use.

Charge-retaining cells (*)
pros: low cost; maintain charge for months when not in use.
cons: Slightly harder to find than standard rechargeables.

Source: http://thenxtstep.com/smf/index.php?topic=899.30