Recommendations for Arduino bot power supply?

Okay, I posted more or less the exact same post over at the Sparkfun forums, but I thought I put it here too to elicit as much feed back as possible.

I'm working on my first robot project. It's a sort of mishmash of some tech stuff that caught my eye.

I started down this road with my interest in learning electronics by working with the Arduino Diecimila. Since that time I have acquired a Nokia N800 Internet Tablet.

I decided I wanted to rig up a simple DIY remote controlled vehicle using Nokia to send commands to the Arduino via Bluetooth. For this purpose I purchased Sparkfun's Blue SMiRF (Silver), a Tamiya Dual Gearbox, and an H-bridge chip.

I've had a lot of fun learning how to put all this together. For the truly curious, check out this post in this thread for a description of what I was trying to accomplish. This post describes what I did up to the point of switching from the hard wired serial cable to the BT connection.

In fact switching from the cable to BT was one of the least complicated aspects of the project. Now I have the first version of my BT vehicle up and running.

My problem is that I currently have two different power supplies: a 9v batter powering the Arduino and a 2AA pack powering the motors. There are a couple of issues with this. First, it is inconvenient to fix the two battery units to the vehicle. Second, the Blue SMiRF seems to draw a lot of power out of the 9V. As I was finalizing the first prototype today, I drained the 9V down to barely more than 7 volts (as indicated by my cheap Radio Shack multimeter). This was below the threshold to power my Blue SMiRF.

So I would like to find a single power supply solution that I can use to replace both the 9V and the 2AA packs. Obviously I would like it to hold the charge for as long as possible. And being rechargeable would be a bonus too. Ideally, the prefect power supply would provide three separate supplies: one for the Arduino and associated Blue SMiRF, and two addition supplies for the two motor controls of the H-bridge.

Does anyone have any suggestions?