The IP address from which you send your request to a search engines website may be regarded as a personally identifying information. In case that this information becomes publicly available the connection between your search terms and your IP address will be visible. In fact, this has happend in the past and there was a searchable database with the leaked information online where you could look up search terms.

I don't know what data Google and Bing are collecting, but here is one quote from the wikipedia entry on internet privacy concerning the AOL search engine:

A search engine takes all of its users and assigns each one a specific ID number. Those in control of the database often keep records of where on the Internet each member has traveled to. AOL’s system is one example. AOL has a database 21 million members deep, each with their own specific ID number. The way that AOLSearch is set up, however, allows for AOL to keep records of all the websites visited by any given member. Even though the true identity of the user isn’t known, a full profile of a member can be made just by using the information stored by AOLSearch. By keeping records of what people query through AOLSearch, the company is able to learn a great deal about them without knowing their names.

Source: http://en.wikipedia.org/wiki/Internet_privacy