12V SLA/gel-cell lead acids are easy to come by in relatively small formfactors and are quite forgiving. Chargers are cheap and easy to get. Batteries Plus and similar sell them at reasonable (but not Internet) prices with no shipping, and they guarantee that they're "fresh", which you aren't going to get from an Internet supplier. Fry's Electronics has them, too, if you have those in your area, but theirs sit on the shelf for years sometimes.
You could also just stack 10 AA Ni-MH batteries together in series (buy a holder) and charge them using a standard Ni-MH charger.
You can work out how long it'll last by taking the battery rating in mA*hr and dividing by 400mA. If the battery is rated in A*hr, multiply by 1000 to get mA*hr (e.g. a 2A*hr battery is a 2000mA*hr battery). If you're putting multiple batteries in series, you use the lowest rated. For multiple identical batteries in parallel, use the sum of the ratings. Don't put different batteries in parallel.
You might ask Randy if those things actually need 12V. If they just have a dropping resistor, a minor modification may let you run it off of e.g. 6V and waste less power.