What I didn't realize is that the browsers have already done things to help us out. If you can forego the need for links you've already visited to change color or background, then the safest option is to turn off visited links. What The Internet Knows About You describes both the underlying issue and some of the possible preventative measures. My favorite...
Firefox 3.5 users will be happy to learn that their browser has a configuration option which disables visited links. To enable it, type in about:config in the address bar and set the
layout.css.visited_links_enabled option to False.
I'd much rather remember which links i visit, than have to discard my browsing history and lose the awesome bar.