If you really want to make sure that EVERYTHING is gone, including the old boot sector partition, you need to use something like Darik's Boot and Nuke from
http://dban.sourceforge.net/ . After you set the system to boot from CD, put this puppy in. It loads a small amount of linux code into the RAM, then wipes the disc entirely, up to DoD standards. Just like new! Use whatever OS disc you want afterward, and you will prompted to format with the appropriate file system.