I haven't read anywhere about replacing the shuffle's battery. In fact I haven't read about anyone's shuffle going bad. If it's under warranty, send it to Apple. If not, it'll probably be cheaper to buy a new one - and by the time your battery dies there will be better and cheaper shuffles (or whatever replaces it) available. I wouldn't worry about it.
)