Ideally instead of a wall of text preceding the use of a service, or even worse hidden away somewhere under a fine-print footer link, I'd like to see services have to do something like this:

"You've just entered some search text. May we store this text and future search queries?

[ ] yes, anonymously to help suggest searches for other users [ ] yes, along with your user name to help refine future searches, and to improve the targeting of our advertising [ ] oh god no, forget I asked"

When clicking a search result:

"Before we redirect you to this page, may we record the fact that you clicked on it?

(similar choices)"

And as they build up history:

"From information you've previously allowed us to save and information we've bought from authorized third parties, we've determined that you are a 35-year old green-skinned right-wing vegetarian with the following sexual fetishes: <redacted>. May we share this information with our advertisers?"

I would hope things would change if permissions were this explicit.