Don't format the Wii, period.
First, what system menu are you on? If it's 4.2 and below, then you can just do this procedure:
1) Upgrade Homebrew Channel to version 1.0.8. (VERY IMPORTANT)
2) Perform a system update to System Menu 4.3. This will effectively remove any cIOS and other items you may have installed into the Wii NAND. Priiloader will also be removed in this process.
3) If you have any forwarder WAD channels on the system menu, use a WAD Manager to uninstall them.
4) If you do not want to have the Homebrew Channel any longer, boot into the HackMii Installer, and uninstall BootMii and the Homebrew Channel itself.
That should take care of the bulk. Remember that there is no way to 'start fresh' (a.k.a. virginize) your Wii after you've installed hacks on it, so if this procedure is simply because you want to "avoid getting detected by Nintendo", it won't help in the end, since the hacks leave traces on the NAND that cannot be removed.