I think I've come up with a great battery solution for the Chumby. It...
1) Fits inside the chumby
2) Can be recharged in 15-30 minutes
3) Gets 5+ hours of Chumby use
4) Costs about $25
5) Easy to make (no soldering required)
6) Uses a standard AA size battery-can be replaced while traveling

Parts list
1) 3 AA 2-slot battery holders with snap connectors (Radio shack part 270-382A) $2 each
2) 4 9-Volt Battery Snap connectors (Radio shack part 270-325) $2/pack of 5.
3) 6 Duracell Rechargeable AA cells (2650mAh) $20/pack of 8
4) Wire strippers
5) Electrical tape

Build instructions
0) Number the battery holders 1-3 and the battery snap connectors 1-4.
1) Strip the wire ends of the 4 9-Volt Battery Snap connectors.
2) Twist the black wire of connector 1 to the red wire of connector 2. Insulate with electrical tape.
3) Twist the black wire of connector 2 to the red wire of connector 3. Insulate with electrical tape.
4) Twist the black wire of connector 3 to the red wire of connector 4. Insulate with electrical tape.
5) Twist the black wire of connector 4 to the red wire of connector 1. Insulate with electrical tape.
NOTE-You should now have a complete chain-looks like an ugly necklace.
6) Plug battery holder 1 into connector 1.
7) Plug battery holder 2 into connector 2.
8) Plug battery holder 3 into connector 3.
9) Place FULLY CHARGED batteries into battery holders following the polarity indicated on the battery holders.
OPTIONAL-With a multimeter, check the voltage of the chain by reading the leads on connector 4. It should read about 7.2V.
10) Open the bottom of the Chumby and remove the bean bag filled with what looks like silica gel beads.
11) With the touchscreen facing away from you, place battery holder 2  on the left side of the chumby between the touchscreen and the daughtercard with the battery cells sitting on top of eachother/stacked/not side-by-side. Place it so the connector is towards the middle of the chumby.
12) Place battery holder 1 on the right side of the chumby on top of the board attached to the touchscreen with the battery cells sitting side-by-side. Place it so the connector is towards the middle of the chumby.
13) Place battery holder 3 right under the opening in the space between the two speakers. This space is about 2 mm too short for it to fit perfectly. Place the non-connector side down first, then place the rest of the battery holder in the chumby.
NOTE-Everything fits very tight, but I was able to get everything to fit without any bulges that affect how the chumby sits.
14) Plug connector 4 into the Chumby's 9V battery plug.
15) Power on the Chumby and enjoy a wireless internet device without wires.

I don't have pictures (my wife is out of town with the camera) but here's a crude drawing of the battery placement.

Looking down on the underside of the Chumby.

                           (Touchscreen)
   ________________________________________
/    _______________                ________________ \
|    |Battery holder 2     \            /  +                            |  |
|    |_______________/            \       Battery Holder  | |
|                                                 /  _    Number 1        |  |
|                                                 \________________|  |
|                    ___________________                           |
|                  /   +                                  |                          |
|                  \       Battery Holder         |                          |
|    ______  /   _      Number 3            |   ________       |
|   |  Spkr  | \____________________| |    Spkr     |      |
\_|______|______________________|________|___/
                         (Back of Chumby)

Notes about testing
1) My chumby performed for 5 hours and 40 minutes on battery power before shutting down.
2) The whole time, the radio was playing at half volume.
3) The chumby was scrolling through widgets which included several photo albums, webcams, clocks, and RSS feeds.
4) The brightness was at full.
5) In the near future, I plan to see how screen brightness, volume, thumbdrive connection, and wifi connection affect battery life.

Notes on recharging
1) I did not include the cost of the charger in the project because that is something I already own. The charger (which recharges 4 cells in under 15 minutes) runs between $30 and $40-I think you get 4 batteries with it. I would recommend buying one anyway-I already have about 10 of the rechargeable batteries throughout the house in remotes, keyboards, and wiimotes. You can't beat the recharge time.
2) To recharge, the battery holders must be removed from the chumby, and the batteries must be removed from the holders.

I will post photos sometime next week. Please feel free to leave comments, questions, suggestions, etc.