It sounds to me as if the only issue is 3rd party ad networks. The antidote to this seems to me to be more reasonably the web browser's jurisdiction, ie. making the cookie policy more restrictive by default.
> Turning off HTTP_REFERER doesn't sound like a very good idea. How would you be able to tell how people found you?
And what if people in general, by default, don't want you to know that and we just got it wrong by default in the browser?
This type of tracking exists for loads of other types of marketing, too. Promo codes, questionnaires that say "where did you find us?" and things like that.
Above all, there's nothing a website can do maliciously with that information alone. An IP address and the page you came in from, that's all there is. The only thing of concern is a feature being provided by the browser which allows spammer.com to write to a cookie that was created by facebook.com right?
I think that sending around the referrer is a necessary part of the interconnectedness of the web. I've noticed in my referral strings before that other bloggers have linked to articles which I wrote, then I've stopped past that blogger's site to have a read of their stuff.
I've noticed a sharp rise recently in services making use of 3rd party cookies, though: FB connect and OAuth generally, and all of Google's stuff (I use a separate browser to stay logged into gmail and calendar so that I'm not logged in as far as Google is concerned for my normal browsing).
What about having sandboxed browser instances which segment off your various web apps in their own little silos?
edit: oops, I see someone beat me to it!