My recollection is a bit fuzzy, but I believe you put the iPod in "data" mode and then connect it to your Mac. You then launch the iPod updater in the utilities file. You can select whether to reformat or update the iPod, I do believe.
Meanwhile, there are very clear directions on how to do this process at Apple.com. On the Support portion of the site. "Reformat iPod" in the search window should yield the info you need.