CSS1で定義されたリンク疑似クラスは、:linkが未訪問リンクに適用され、:visitedが訪問済みリンクに適用されます。

この二つのリンク疑似クラスは、同時に適用される事が無いため、同じ要素に同時に適用される事は有りません。
また、訪問済みリンクを示す:visitedは、ある程度の時間が経過すればUA（ブラウザなど）側で判断して未訪問リンクである、:linkの状態に戻しても良いとなっています。

対応ブラウザ

• 
• 
• 
• 
• 
• 
• 

リンク擬似クラスのサンプル

a:link {
  background: #ffffd6;
  text-decoration: underline;
}

a:visited {
  background: #f1e8fd;
  text-decoration: underline;
}

<p>以下のリンクは
「<a href="http://digiper.com/">digiper</a>」に
関係のありそうなサイトです。</p>
<ul>
<li><a href="http://css-happylife.com/">CSS HappyLife</a></li>
<li><a href="http://digiper.com/kirilog/">KiriLog</a></li>
<li><a href="http://hyper-text.org/">WWW WATCH</a></li>
<li><a href="http://mote-career.com/">モテキャリ☆</a></li>
<li><a href="http://bb-to-ab.com/">Ｂ to Ａ</a></li>
</ul>

未訪問リンクでは背景色を薄い黄色にし、訪問済みリンクでは背景色を薄い紫にしています。

このサンプルを今見ているブラウザで表示すると以下のようになります。

サンプルのブラウザ上の表示

以下のリンクは「digiper」に関係のありそうなサイトです。

• CSS HappyLife
• digiper
• KiriLog
• WWW WATCH
• モテキャリ☆
• Ｂ to Ａ

いずれのリンクも訪問済みになっていない場合は適当なリンク先をクリックして更新ボタンを押してもらえば変わるのが確認できます。

リンク疑似クラスを使う事で、自由に未訪問・訪問済みリンクのスタイルを適用させることが可能ですが、未訪問と訪問済みが明確に分かるような指定をしましょう。
いくつかの例外は有りますが、特に本文の文字色とあまり変わらない、もしくは同じ色の指定は、ユーザビリティを下げるだけでなく、そもそもクリックしてもらえないという意味の無いリンクになってしまう可能性も有るので注意が必要です。
やり方がひどいと、SEOスパムとも取られる可能性も有るので尚更ご注意を。

もちろん、デザイン上の都合で色を変える事は必要だと思いますが、ウェブサイトは使ってナンボです。