Resource Articles:

1. Wall Street Journal: Should Web Search Data Be Stored?
   Key point: Kevin Bankston of EFF argues “Average Internet users probably don’t even realize that AOL, Google, etc. are keeping logs of their searches, logs which in many if not most cases are linkable to a particular user. And even if they do realize that, they still have no idea how long that data is stored, nor what exactly is done with it, nor with whom it is actually shared.” 
2. Electronic Frontier Foundation: How To Keep Your Search History Private
   Very few average users would know how to shut off cookies for a few sites. If they shut off cookies for all, they would lose access to many of the features they want and would be constantly harrassed with dialogs requesting they activate cookies. As for using an anonymizing proxy, or proxy network like Tor, to prevent search engines from learning your IP address, that well exceeds their effort threshold.