Apple - Batteries - iPod. A good section on iPod battery life. Basically it says that an iPod can go through 400 cycles before you get to 80% of maximum battery life. All batteries have a life and these definitely do.
A cycle by the way is a complete all the way and all the way down. It is a little confusing, but if you listen half way down and then recharge and then go down half way, that is a full cycle. Also mentions that you should cycle through the battery at least once because the battery is chemical thing and needs to be cycled.
Takes by the way 2 hours to charge to 80% of capacity and then another 2 hours to trickle charge to 100%. Net, net, when you buy a used iPod, you may have something that won't go as long as the 20 hours for the Ipod, 14 hours for the nano and 12 hours for the Shuffle (personally I've never gotten anywhere close to any of these figures, but maybe others are luckier).