Powering Arduino with Solar Panels
First of all you want to buy some solar panels or cells. Although they can be found on eBay for very cheap, but they not be as efficient as they say. I would say try to buy from a reputable dealer to see reviews on the product or trust that they work efficiently. Sparkfun datasheets are generally accurate and can be trusted.


Most optimal configuration: Do not use a regulator and some sort of step-up booster. Try the TPS61200 or TPS61202 chips. They will not regulate the voltage, they boost the voltage dynamically. This is much more efficient and therefore generates less heat. They work like a reverse voltage regulator, taking .3V to 5.5V and turning it into anywhere from 1.8V to 5V (xxx0) or 5V exactly (xxx2). Hack a USB B end and just connect the power lines to the Arduino.
Discharge/charge simultaneously: Yes, however I'm not sure how to. I believe that if you hook up a charger IC and a load, the voltage won't go through the battery, it will go through the path of least resistance. However, your battery wouldn't get charged then. This is outside the scope of the question, so I would recommend EE on how exactly to do this.
Is LiPO the best: Try a Lithium-Ion Battery. (A.K.A. Li-ion) According to this site:


  Although the lithium-polymer battery is sleeker and thinner, lithium-ion batteries have a higher energy density and cost less to manufacture.


Therefore, it seems like Li-ion is the best choice for you. Note: Since you are dealing with very dense batteries that if overvolted can go up into flames [Note: please mute your speakers!], make sure to go with Sparkfun/Adafruit/etc...
Economic way: If you don't mind a big "homemade" solar panel, go this way. Buy through eBay or a similar site solar cells. They are small plates that are connected to create a solar panel. Try looking for "grade B" or similar solar cells that work fine, they just may have minor imperfections. It won't be as pretty, but you'll save some cash.


See this EE.SE post for more information. One cool thing that I saw was:


  This is really cool. You can connect the Li-Ion voltage through an op-amp to generate a pulse wave, which can be picked up by your MPU to tell your bot to go charge –  Raaj Oct 18 '13 at 18:44


I'm not exactly sure how to do this, but it might be useful. I couldn't find anything online about it.