Try to use another browser than IE to search... like
Firefox It will probably not be affected by the hijacker.
On the other hand try to disable any suspicious entry in the startup configuration. Start > Run > "msconfig" Make sure you restart after any change to verify that it did work.
If you have Windows XP you should also take a look at the "services.msc" to see if there's a suspicious service (hide all Microsoft services to se it clearlier) If there is, disable it and set the start to manual.
Search in your Uninstall list if there's an entry to this program and try to uninstall it. If not search the programfolder and run the unwise.exe / uninstal.exe / remove.exe in the folder if any.
Any other way would envolve Ad-aware or similar, wich are not always the best solution to deleteing spam-/ad-/spy- ware but at least the are effective (some garbage may be left in the registry or in other folders, nevertheless).
Good luck!