I don't remember anyone ever discussing the referrer as being an issue before 3rd party ad networks became so prevalent.
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?