I've reset my own iPod using iTunes several times (for various reasons).
With iTunes open, plug in your iPod. Once it's been recognized, you'll see a 'reset to factory settings' option in iTunes (not the exact wording but you get the gist). Select that option, and the sotware will reformat the iPod for you. Afterwards, you can resync your media files.
It's been a fairly painless (though time-consuming) activity each time I had to do it.