When the iPod is plugged into iTunes, press Restore. Everything on the iPod will be erased, and the software will be reset to factory settings.
Here's a picture of how to do that:
http://www.flickr.com/photos/15919521@N05/2860380348/
The "uncheck songs" method, which seems to be so popular on here, is more for picking and choosing which songs you want if you don't have enough room, or stuff like that.
Bookmarks