I'm looking for a battery shield for my Arduino Duemilanove. I would be asking "what's the best" but everything I find is out of stock except for this which is USD77.86 with the cheapest freight to Australia. So instead I'm asking "is there anything?" I'd prefer a solar-panel capable shield, but really I'll take anything that's rechargeable.
Sure: Get this and this from Digikey (or their equivalents from your favorite distributor), and mount it to some perfboard! This is another option for an integrated clip/holder. Do you really need the rechargeable Lithium battery you linked? $70 buys a lot of 9-volts.
If you want to go for it, powering your device with a solar panel the size of the Arduino (.004m^2, or 40cm^2) will not be trivial. In the continental US, the sun puts out about 1kW/m^2 at noon on the brightest day of the year, but a solar panel will only be about 20% efficient, and you'll average about 20% of that peak power, so you'll get about 160mW from your shield, or about 3.2mA at 5V. Unfortunately, this power is not available at 5V - A solar cell puts out less than 0.5V. Putting the cells in series is possible, but you can't just draw power from them like a PSU. You'll need a switching regulator, and you'll probably want to bypass the 7805 on the Arduino for this (or tap into the USB Vbus line). Linear Technology makes a number of switching regulators for energy harvesting devices. I doubt that the components required will be availabe in through-hole configurations. You'll also need a battery and/or supercap to accumulate the charge from the panel.
Other mods you'll want to do are to remove indicator LEDs from your board, put the FTDI chip to sleep (pull pin 12 up with a resistor to 5V when you're not programming it), and to make sure any other shields you're using draw as little power as possible. In software, make sure you have no busy waits or polling loops (this may be a big change in programming style), and put the chip to sleep if you're not in an ISR. See this page running an Arduino on low power for years, and this one for some code.
It can be done, but it would be tricky! This would not be a shield for beginners.