Andy,
To help answer some of your questions: I use an Oly-3040 with GP 1800 batteries. My dives are normally each an hour long and I have no problem shooting approx. 100 photos in total between both dives and I'll still have about 15 minutes of time left to review them. A couple of things to note: Although I have used quite a few of smart microprocessor controlled chargers, none seem to charge up the batteries as well as my SLOW Energizer charger. I have confirmed with some battery makers that slow charging your batteries will allow them to take in more of a charge. Makes a difference when you start missing that end of your second dive, once-in-a-lifetime shot. I also shoot with my camera's strobe set at -2. Turning off your LCD inbetween shots will also help you conserve even more battery power.
As Jeff (Sharpdiver) was mentioning, the Olympus 3040/4040 has a macro 'sweet spot' that will allow you to get ~4 inches away from your subject. How close can you get without a macro lens? Here's an example:

One small correction to Jeff's statement. You need to zoom in all the way and slightly tap the zoom/wideangle level four times. Then simply move the camera back and forth a tiny amount until the subject falls into focus. (I'll talk about focus in just a minute)
With the addition of a macro lens (Sea & Sea and Inon) you can expect to get much closer.

Shot with a Sea & Sea 3T lens.
I shoot with a 128MB card in HQ mode--I have yet to see a noticeable difference between SHQ and HQ--and I get 164 photos per chip. This is on the 3040 camera, which is 3.3 megapixels.
Now, on the subject of focusing. I have a bit of a different opinion. There are a couple of tricks that will definitely allow you to get that subject in focus. The one that is well known is the full time auto focus. Works well and it even slightly reduces the shutter lag but it eats up your batteries---no good in my opinion.
There is also the LED confirmation Nick mentioned.
Here are a couple of things I do, especially when shooting macro. Hit the zoom/wideangle lever while having your subject in frame--the camera will automatically focus on the subject. Shoot in manual mode and when you bring the zoom down to below 8-inches the LCD will zoom in...this helps me out immensely in my macro shots. And last, but definitely not least, once you've taken you photograph you can go back and preview it and zoom in up to 3x. This will give you a pretty good idea if your shot is in focus. Either way, just like you'd do in film (without the cost of wasted film)---shoot, reshoot, and reshoot some more. The more shots you take of the same subject the better your odds of a good photo.
If you're going to be shooting in shallow waters, attaching a small hood to the camera would be advisable. With it, you should have no problem seeing the LCD.
There are quite a few tricks to using the Oly cameras and I feel that with its aperture range (16 positions) and its shutter range (36 postions)---these camera offers a variety of exposure capabilities--well worth the few bucks.
My 2 cents.