WordPress 2.5 以降では、query_posts() 等で記事を取得する際に orderby=rand という引数を与えると、取得記事のソート順をランダムにしてくれます。
それを使って、過去記事からランダムに1件だけ取り出してオススメする方法。

以下のコードをテンプレートのお好きなところに貼り付けてください。

<?php $newquery = new WP_Query('showposts=1&orderby=rand'); ?>
<?php if ($newquery->have_posts()): while ($newquery->have_posts()) : ?>
<?php $newquery->the_post(); ?>
<a href="<?php the_permalink(); ?>" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a>
<?php endwhile; endif; ?>
<?php unset($newquery); ?>

一応、簡単な説明。

1行目の showposts=1 で、1件だけ取り出すように指定しています。
複数件呼び出したいときは、ここを showposts=5 などとすれば、おっけ。

2〜5行目でループしてます。
ループ外に何か (<ul> タグなど) を書きたいときは、この外に。

4行目で、リンクを書き出しています。
リンクの形式を書き換えたいときは、こちらを修正してください。