For batteries you could look at the following options for different batteries and some simple ideas for charginghttp://www.batteryspace.com/lifepo4cellspacks.aspx
The benefit of LiFePO4 is life time number of discharges, and safety. They are being designed for ElectricVehicles
LiIon has good energy density, safety issues, and lifetime issues, but not as bad as NiMH
NiMH has lifetime discharge memory
All rechargeable batteries can be used in series - that is solar panel to LiFeP04 charger -> LiFePO4 batteries -> your board.
However you need to understand the voltage range of the battery technology - for LiFePO4 its 3.7V fully charger to about 2.5V for LVD (Low Voltage Disconnect) to preserve the life of the battery.
Basically unless you use a standard battery pack that does this for you, you are going to need to do some engineering.
There are some SolarLed Lighting products that have integrated solar panels and LiFePO4 batteries that if you can live with the power budget might do everything for you.
lowes.com "Portfolio 3-Pack Black Solar-Powered LED SpotLights" - by my experiment the solar panel is under powered and the batteries on a full daily charge/discharge cycle are loosing capacity.
I'm looking at a project and specifying
1) Total power budget for 7 days - this sizes the battery
2) Expect there to be 7 days of inclement weather with no solar and when the sun returns recharge in 4hrs - this sizes the solar panel
The big issue with standard Arduino boards I've seen is they are not built for battery powering - the DC regulators and always on LEDs - so my criteria is for the hardware to be put to sleep - and have a low quiescent power usage of less than 0.5mA.
The Teensy3.1 has some powering metrics that are in the uA and a good starting point for a battery powered board.
Back some years ago, I rolled my own Mega2560 board and interfaced it to a cellular module which required bursts of 1.2A@5V for transmit and 700mA for Rx. Overall it took 1minute to make a cellphone connection and transmit data. The cellphone was on a 1hr reporting schedule, the quiescent power of the board asleep was about 0.7mA
I powered it off a 2.2ALiIon battery and I think a 6Watt solar panel and its been very successful, it was a lot of work in software to manage the power.
Arduino software/libs - which prioritizes ease of understanding and is fantastic for accessibility - however so far I've not seen any priority for power management. From what I've seen using yield() makes it challanging to create algorithims to do power management. TinyOs.net "wireless networking" has some documents together on power management algorithms - however they are engineering concepts. Linix 3.8+ is also evolving power management capabilities