I've dealt with every form of spyware under the sun, from simple hosts file redirections to junkware replacing winsock DLL files, to browser hijackers and keyloggers. What you have here is a combo BHO (Browser Helper Object), and Toolbar. The first step to revival is to download
HijackThis. Open it up, and click "Scan." As others have suggested, click "Save Log", open up that file, and copy/paste the results here for us to examine. Otherwise, in the checklist that comes up, check off anything that says BHO and Toolbar, and click "Fix Checked." It might warn you that you must close all IE windows for a BHO to be removed, so you'll want everything closed except HijackThis when you do that. After it's all set, try opening up IE, and see if it's gone. If it's still there, we'll have a look at the log file, and suggest some registry changes to manually remove the bugger. (I've noticed HijackThis can and does effectively remove toolbars from HKEY_LOCAL_MACHINE but not from HKEY_CURRENT_USER, and often I have to remove toolbar entries from there manually).
Good luck, and keep us informed!