If you buy a battery pack with built-in over voltage protection (pretty standard for any Li-ion battery pack) then you can connect the solar panel directly to the battery if you confirm that the solar panel can not produce more current than the battery can accept. The conservative estimate here would be max rated power of the solar panel divided by the under-voltage threshold of the battery protection circuit. This calculated value should be >> than the max charge current specification of the battery. batteryspace.com has a wide verity of batteries and is generally good about specifying the information you will need.
If you want to maximize efficiency you can dive into the world of solar cell peak power tracking, which would be a circuit you insert between the solar cell and the battery to deliver the maximum power achievable from the solar cell. There are dedicated ASICs (Linear Tech and ST micro), or you can design your own hardware and algorithm with an MCU.
Battery fuel gauging including counting electrons, (or coulomb counting) can get really complicated before it will give you consistently accurate results over time, temperature and cell ageing. Luckily, many applications can get-by using battery voltage as an indicator of state of charge; it sounds like your application may fit in that bucket.
As for controlling when your lights turn on and off, you can use a comparator with hysteresis. As an example, if you have a single-cell Li-ion battery pack, you can expect the voltage to vary (nonlinearly) with state of charge between about 3.3V and 4.2V; so you would set your comparator to toggle on at 4.1V and toggle off at 3.4V (you can play with those values depending on your consideration of cycle-life vs. depth of discharge).
Here is the first google result for more information on a comparator with hysteresis, but there are a lot of different ways to implement.
http://www.ti.com/lit/ug/tidu020a/tidu020a.pdf