The small but tech-savvy sample group said search engines could regain their trust in two ways. One would be to quit storing data entered by searchers altogether. The other would be to grant users editing permission on the data the search engines retain.

Riza C. Berkan of Hakia said, "It is not the data or cookies… it is the intent in handling them. The problem is purely in communications. Search engines must openly declare what they are doing with the data and all tracking devices, almost like a confession. Alternatively, they can ask users’ permission when the data is being captured and the privacy line could be seemingly crossed. Once such clarity is exercised, then it is a fair environment." 

Via eMarketer