I guess you are using IE6. Click on Tools>Internet Options.
Click on the Contents tab. Click on AutoComplete. Uncheck Forms there.
If the search history doesn't go off, you will have to delete it manually.
Say you open up google, and type a there and your previous searches pop-up, hit your down arrow key and press delete. You would need to do that for all your previous searches