Wait 'till the battery is completely drained, then charge it fully. Wash, rinse, repeat.
EDIT: You know all those people who bitched about the fact that their iPod batteries were crapping out, and sued Apple? I'm not one of them. My original 5 GB iPod ONLY NOW is beginning to show signs of not holding a decent charge because of the way I treat it.