The exact same thing happened to my iPod mini after a year as well - 20 minute battery life!
Fortunately I took out a £1.99 a month insurance at PCWorld when I bought it. They exchanged it for a 4gb Nano at no extra cost
But if I hadn't had the insurance I'd have to change the battery. Look in Google for ...ipod, battery, change... there's quite a few resources describing what to do, and many places to buy replacement batteries.
I think it's quite awkwark to change - basically you have to carefully cut the glue out of the sealed ends of the iPod, take out the board inside and remove & replace the battery. But can be messy if not careful.