JavaScriptを使わずにWebブラウザの閲覧履歴を盗む - スラッシュドット・ジャパン デモページの解説によると、このWeb閲覧履歴を「盗む」テクニックはCSSを利用するもので、あらかじめページ内にそのユーザーが訪問しているかをチェックしたいURLを仕込んでおき、CSSを使ってそのURLを過去に訪れているかを調べるというもの。
仕様に脆弱性があると言う話で昔から知られてはいたのだけど、最近になって「ad4U」などのサービスが出てきて問題視されだしたというもの。

ちなみに、Firefox 3.5 Previewでは「layout.css.visited_links_enabled」を「false」にすることで防げますが、代償として訪問済みのリンクの色が変化しないので、訪問済みか見た目で分からなくなります。
（※Firefox 4では対策済みですので設定する必要はありません。 ）

それと、Firefox 3.5 Previewからは犠牲（履歴を捨ててplaces.sqliteを作り直す）なしにバージョンダウンできませんので注意。

参考：気の早い宣伝 - JavaScriptを使わずにWebブラウザの閲覧履歴を盗む

関連：
ブラウザーのバグを利用した行動追跡
ブラウザーのバグを利用した行動追跡：追記
ブラウザの閲覧履歴を盗まれないようにする必要性
行動ターゲティング広告対策について