First, everyone assumed that no one knew knew about anything they did on the net. They thought that when they looked at an oven mitt in an online store, only they knew about it. The truth was that information was just unused by the store, and so the user never saw it.
Gradually, this notion became slowly dispelled when stores actually started leveraging this information to provide, for example, suggestions. It's all fine and good here.
Finally came targeted ads. The part that people find terrifying is when the suggestions are "following them around!". This is creepy in multiple aspects:
The first is that people don't quite understand how this happens (of course, we do). How is this information showing up in different websites? Did the store just let these other sites handle my information? In their eyes, the boundaries for who is allowed to my personal information seem to blur. This also breaks the paradigm of location that the user has in their mind. "If I don't go to site X that is, I won't see anything about site X." It looks like everyone knows everything.
The second is that it's creepy-through-analogy. The fact that it's going wherever you're going and nagging you constantly is weird. When I walk into a retail store, I'm usually asked if I want any help, and I decline politely. If, however, the salesperson keeps approaching me and trying to sell me things that I don't want, I get the fuck out. With targeted ads, the average user can't do that! The creepy sales guy is following you out to the street and into your home. This usually ends in extreme frustration.
Finally, there are also some nuances that targeted ads miss. Targeted adds are actually not that targeted, they're just there to grab at the "low hanging fruit" customers that are on the verge of making a decision. Just because I looked at a dildo once because I thought it was funny doesn't mean I want to be bombarded with the world's finest penis emulators for the next 3 days.