Well, that info (about overcharging) from the Nokia leaflet is wrong, it's some old rubbish left over back from when Nokia used Ni-MH batteries. They still keep printing that for everything they make, for some reason.
There is circuitry in the N800 (and all li-ion battery devices) to stop charging when the battery is full, the reason being that the battery would explode if overcharged. That simply must not happen, so in addition to the N800 circuitry there's also a final overcharge protector inside the battery itself.
On the other hand, the battery lifetime _will_ be somewhate reduced if at 100% all the time (much more so in a hot environment, ref. the already mentioned laptops).
The battery capacity of the N800 is good enough to use it on battery for a day or several days even. But when you see the bars dropping feel free to charge it, that won't harm it. Just avoid discharging the battery all the way, because that _will_ in time reduce the lifetime/capacity. (But again, the N800 as well as the battery has discharge protection too, because discharge too much and the battery is destroyed. You don't want to trigger the built-in battery circuit though, as it takes special equipment to get the battery working afterwards. The N800 circuitry will step in first though.)

Use the (i) and (ii) in convulted's posting as good rules of thumb.