A small 2-cell lipo (7.4V pack) with a 5V regulator following that - ultimately you start to find that it's just 'cheaper/simpler' to go to somewhere like DealExtreme and pick up a prefabbed solar battery solution with USB output.
http://www.dealextreme.com/details.dx/sku.30012 (just search for "solar usb" and be prepared to be awash with options). Looks like the decent ones start at about $50 where's the cheap are as low as $8.
Paul.