I almost missed this one as there was an obscure post relating to MSN and they mentioned it as an aside but Google now has a new way to help you manage your search history.
If you go to Google labs you'll find a new tool called "My Search History" which, when clicked on, allows you to sign into your Gmail account (or create a Google account) and it will store your search history for you. From what terms you searched for but didn't click on any results, to those sites you did visit when clicking on results.
It only seems to work on the main Google search results (no images, news or groups yet) and doesn't seem to work on other regional Google sites (such as Google.ca). But again, I'm sure that will come with time.