The EFF has an online article showing how to clear and pause your web search history in a few simple steps.
However, this didn't work for me; when I tried to direct my browser to https://google.com/history, as instructed, I was automatically redirected to my iGoogle page.
What I did instead: I clicked the gear symbol in the upper right corner and selected "Web History". That had the same effect.
The EFF encourages us to do this before March 1st, when Googles new privacy policy takes effect. But if you read this after March 1st, do it anyway; the less they know about your habits, the better.
Hat tip to Beelzebjörn (in Swedish).