1. First, hit Start> Run> regedit (type and hit enter or press Ok). Now regedit will launch.
2. Now, click on HKEY_LOCAL_MACHINE and then click SOFTWARE.
3. A large list of folders will present themselves in front of you, find the folder named Microsoft, and click it, yet another list of folders will open within Microsoft, scroll down until you find Internet Explorer.
4. Even more folders will present themselves, this is for the last time. Scroll down and find Search (you will notice this has NOT got a + sign next to it.)
5. Click Search and there will be 2 variables, "CustomizeSearch" and "SearchAssistant". For now right-click just "CustomizeSearch" and select "Modify".
6. Now you will notice that you can 'modify' the Value Data field. Enter the URL of your desired search engine (eg. http://www.google.com for Google, or http://www.altavista.com for AltaVista.) After you have done this click Ok.
7. Do the same as above (Step 6) with the "SearchAssistant", and then exit regedit.
8. Load up Internet Explorer and click on your search icon, now, if all has been done correctly you should see the search engine you entered.
Remember, it is always a good idea to make a back-up if you are changing anything, just incase something goes wrong.
I would reccomend Google as the search engine of your choice!