Advertisers use what information they have to try to best guess what sort of ads you will be most interested in. In Google's case, your search history is the best indicator they have, but ad clicks and ad impressions are also considered. In Amazon's case, for example, your purchase and product browsing history is their best indicator, and you'll probably notice that their suggestions closely mirror your recent history — even if that most recent history dates back to two years ago.
My own search and browsing habits tend to favor highly technical content; servers, programming, malware, etc. The ads I see when browsing under that profile therefore tend to also favor technical content: colocation, hosting, software, etc. This is totally Fine By Me™. When I watch TV, I have to endure a depressing amount of ads about feminine incontinence, retirement homes, and herpes medication. But on the Internet, the ads are all software and servers. Do I think that's creepy? Hell no. The fewer herpes ads the better, IMO.
To be clear: I'm a strong proponent of online privacy. However, I manage my online privacy by controlling the information I make available online. I don't expect others to maintain my privacy for me; the concept doesn't even make sense. If you don't want them to know something, then don't tell them. Telling them and then demanding that they forget is a recipe for disaster on numerous fronts, and even comical from a security standpoint.
If I don't want a search associated with me, I use a private browsing session, possibly from a different IP if I were to be worried about something. Sure, I could use a service that promises to not remember what I tell them, but I would be an idiot if I were to depend on that promise. Remember Hushmail? Still, I prefer to use a service that allows me to craft my own online preference profile so that they can filter out all the crap I clearly don't want.
Is this legal? — So far yes. I would hope that it remains so, since the unintended consequences of making it illegal would be so far reaching and unexpected that it would have devastating consequences for completely innocent Internet users and site operators. Internet regulation reliably makes things worse.
Does this bother me? — Of course not. If I buy an apple from a market, is it creepy for the vendor to ask me the next day whether I liked my apple? Do I think he's spying on me? If I tell him I liked it, is it creepy for him to suggest that I buy more apples at a subsequent visit? No, of course not. It's just good customer service. If he tells the fruit vendor next door that I like apples, should that be illegal? Of course not: It's his information to give, just like any conclusions I make about him are my information to share as I see fit.
Vendors online remember what we tell them just like vendors at your local market. My fruit vendor may remember that I visited his store even though I didn't buy anything, and yet I don't assume that he's spying on me. I'm visiting him, not the other way around. Likewise, when I visit Google, I don't think it's spying for them to remember what I ask them.
The biggest problem with online privacy is the implicit belief that because I connect to the Internet from the privacy of my own home, anything I do on the Internet also happens in the privacy of my own home. This is lunacy. Everything you do on the Internet is absolutely public unless you can verifiably prove otherwise.
