charging rechargeable batteries

is it better to wait until batteries are depleted fully, and then recharging, OR is it fine to recharge batteries when it's half full or partly full?
i'm referring mostly to laptops, mp3 players, phones and the like. i guess i'm slightly concerned about improper charging.

>>5
I take it that Lithium Ion is the kind of battery one finds in a laptop, right?