For Agent and Toolbar variants, the CommonName entry in the Control Panel's Add/Remove Programs option should work fine. In CommonName/Mib, unfortunately, this just sends you to a page on CommonName's web site, which requires a working Internet Explorer with ActiveX downloads enabled to function.
For CommonName/Toolbar and CommonName/Agent: before being able to delete the CommonName files, you must deregister CNBabe.dll. To do this, open a DOS command prompt window (from Start->Programs->Accessories) and enter the following commands:
cd "%WinDir%\System"
regsvr32 /u "C:\Program Files\CommonName\Toolbar\CNBabe.dll"
(Change the filename above if your Program Files folder is somewhere other than 'C:\Program Files' - for example if you are using a different drive, or a non-English version of Windows.)
Reboot and you should be able to delete the CommonName folder in Program Files. You can use Internet Options->Programs->Reset Web Settings to restore the normal search options.
CommonName/Mib: do not try to uninstall this variant by just deleting the files. It includes a WinSock2 LSP, deletion of which will cause your network connection to die!
The first step to removing the Mib variant is to deregister this LSP. The easiest way I know of is to run the tool LSPFix. Tell it to 'Remove' CNMib.dll (and 'Keep' everything else).
Next, you need to deregister the CNBabe DLL. This is harder than in the other variants as it will constantly try to re-register itself to make it hard to get rid of.
Open the registry (Start->Run->regedit). Close all other windows — in particular there must be no Windows Explorer or IE windows open. Open the key HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\. Inside this key you must delete the subkey Explorer\Browser Helper Objects\{00000000-0000-0000-0000-000000000000} and the value 'Zenet' in the subkey 'Run'. Then reboot immediately.
You should then be able to delete the entire CommonName folder in Program Files. You can use Internet Options->Programs->Reset Web Settings to restore the normal search options. Finally you can clean up by deleting the following registry keys:
HKEY_LOCAL_MACHINE\Software\CommonName
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\MenuExt\Add A Page Note
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\MenuExt\Bookmark This Page
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\MenuExt\Email This Link
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\MenuExt\Search using CommonName
HKEY_CLASSES_ROOT\BabeIE.Helper
HKEY_CLASSES_ROOT\BabeIE.Helper.1
HKEY_CLASSES_ROOT\BabeIE.AgentIE
HKEY_CLASSES_ROOT\BabeIE.AgentIE.1
HKEY_CLASSES_ROOT\BabeIE.Handler
HKEY_CLASSES_ROOT\BabeIE.Handler.1
HKEY_CLASSES_ROOT\CLSID\{00000000-0000-0000-0000-000000000000}
HKEY_CLASSES_ROOT\CLSID\{6656b666-992f-4d74-8588-8ca69e97d90c}
HKEY_CLASSES_ROOT\CLSID\{9346A6BB-1ED0-4174-AFB4-13CD4EC0AA40}
HKEY_CLASSES_ROOT\TypeLib\{D879D743-E2CC-4161-8034-2234203681C9}
HKEY_CLASSES_ROOT\Protocols\Handler\cn