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.

Lithium Ion - Recharge whenever you can, fully draining the battery damages its capacity.
NiMH/NiCd - Let them drain fully before recharging, recharging when there is still a charge left will damage the capacity.