Go for a Ni-MH battery. They are easier to charge as they don't have a 'memory' and they usally have a higher capacity than Ni-Cad so they shouldn't run down as fast.

More info I got off a site...

Ni-Cad

Ni-Cads are the lowest cost option when purchasing rechargable batteries, they also have the lowest energy density i.e. hold the least charge when compared to equivalent batteries of different chemistrys. NiCads suffer from memory effect i.e. they should be completely discharged before recharging. They are available in all the common consumer sizes as well as specialised industrial sizes and packs. They are comparatively slow at charging and not considered enivronmentally freindly due to thier Cadmium metal content.

Ni-MH

Ni-MH are the more expensive than NiCad but cheaper than Li-Ions. They have superseeded NiCads as the consumer rechargable of choice as they have many advantages. They have a higher energy density giving them much more power delivery, they can be charged very quickly they are less harmful on the environment, they do not suffer from memory effect. They are available in the same sizes and shapes as NiCad.
Li-Ion