Get Nickel Metal Hydrides with the highest mAh rating possible.
You can get 4 AA plus a charger for £20 in Dixons. Make sure it says "Photo" or "High Drain Device" and get mAh of 1800 or above. The higher that numebr the longer they last.
Got 4 AA 1700mAh in my camera. Takes about 250 - 300 shots (50% with flash) before drianed.