This EFF document clears some things up.
And while that document is instructions for “removing your google search history” before the new policy takes effect (which has been going around facebook lately, as these things tend to do, true or false), they’ve added an important note at the bottom saying that, well, you can’t, really.
Note that disabling Web History in your Google account will not prevent Google from gathering and storing this information and using it for internal purposes. It also does not change the fact that any information gathered and stored by Google could be soughtby law enforcement.
With Web History enabled, Google will keep these records indefinitely; with it disabled, they will be partially anonymized after 18 months, and certain kinds of uses, including sending you customized search results, will be prevented. If you want to do more to reduce the records Google keeps, the advice in EFF’s Six Tips to Protect Your Search Privacy white paper remains relevant.
[None of the tips in the related document are particularly feasible for the gmail-using google-search-using person who doesn't want to jump through hoops quitting browsers all the time]