１．プラグインのセット
こちらからPHP PreviousNextInCategoryをダウンロードします。解凍すると「block.MTEntryNextInCategory.php」と「block.MTEntryPreviousInCategory.php」の２つのファイルが出てきます。これをMT本体をインストールした場所にある「php」フォルダの中の「plugins」ディレクトリにアップします。

２．カテゴリ内での前後リンクのタグ
以下のタグをエントリーアーカイブの好きなところに追加します。

<MTEntryPreviousInCategory>
<a href="<$MTEntryPermalink$>">&laquo; <$MTEntryTitle$></a> | </MTEntryPreviousInCategory>
<a href="<$MTEntryLink archive_type="Category"$>"><$MTEntryCategory$></a>
<MTEntryNextInCategory>
| <a href="<$MTEntryPermalink$>"><$MTEntryTitle$> &raquo;</a>
</MTEntryNextInCategory>

たったこれだけ！で完了です。ストレートに使えるプラグインはやっぱりいいものですね～。

なお、関連情報の載っているサイトなどを見てまわると、このプラグインではメインカテゴリでの前後リンクしか表示されないので、複数カテゴリを使っている場合にはちょっと苦しいみたいです。修正して工夫されている方々もおられるようですが。ちなみに静的生成では１つ前の記事に自動でリンクを出現させるのにかなり苦労するみたいなので、どちらかというとダイナミック向けのカスタマイズかも。

参考にさせていただいたサイト（複数カテゴリ用の修正記事もあります）
カテゴリー内の前後のエントリーへのナビ(PHP)

■MT4への修正方法（2007.11追記）
3.3用PHPプラグインはそのままではMT4には使えません。いずれ配布サイトが対応してくれると思いますが、それまでにこのプラグインをMT4で使いたい方のために修正方法を覚え書きしておきます。行数は3.3用ファイルのもので書いています。
参考：ダイナミック・パブリッシング対応プラグインの MT4 における仕様変更について

このプラグインはphp/lib/以下にあるblock.mtentrynext.php・block.mtentryprevious.phpと同じ作りになっているのですが、3.35と4.0でこのファイルに変更があったため、ファイル名だけでなく、内容も同じ個所を変更する必要があるのでそれも合わせて載せています。

block.mtentrynextincategory.php
まず、ファイル名のblock.MTEntryNextInCategory.phpを全て小文字に変えて下さい。
オリジナルファイルの以下の行数に相当する個所に赤字の部分を追加・変更します。

13行目

function smarty_block_MTEntryNextInCategory($args, $content, &$ctx, &$repeat) {
　　　　　　　　　　↓
function smarty_block_mtentrynextincategory($args, $content, &$ctx, &$repeat) {

24行目～

$ts = $entry['entry_created_on'];
$blog_id = $entry['entry_blog_id'];
　　　　　　　　　　↓
$ts = $entry['entry_authored_on'];
$blog_id = $entry['entry_blog_id'];
if (isset($args['class'])) {
$class = $args['class'];
} else {
$class = 'entry';
}

36行目～

'sort_order' => 'ascend',
'current_timestamp' => $ts);
　　　　　　　　　　↓
'base_sort_order' => 'ascend',
'current_timestamp' => $ts,
'class' => $class);

block.mtentrypreviousincategory.php
まず、ファイル名のblock.MTEntryPreviousInCategory.phpを全て小文字に変えて下さい。
オリジナルファイルの以下の行数に相当する個所に赤字の部分を追加・変更します。

14行目

function smarty_block_MTEntryPreviousInCategory($args, $content, &$ctx, &$repeat) {
　　　　　　　　　　↓
function smarty_block_mtentrypreviousincategory($args, $content, &$ctx, &$repeat) {

24行目～

$ts = $entry['entry_created_on'];
$blog_id = $entry['entry_blog_id'];
　　　　　　　　　　↓
$ts = $entry['entry_authored_on'];
$blog_id = $entry['entry_blog_id'];
if (isset($args['class'])) {
$class = $args['class'];
} else {
$class = 'entry';
}

36行目～

'blog_id' => $blog_id);
　　　　　↓
'blog_id' => $blog_id,
'class' => $class);

よろしくです。

＜2008.7.1　追記＞
MT4からはプラグインを使わずMTタグだけで同じことが出来るようになったので、その方法も追加しました。
4.0～　同一カテゴリー内での前後エントリーへのリンク(３)改 MT4.0～
4.1～　同一カテゴリー内での前後エントリーへのリンク(2) MT4.1～