CentOS4にはnkfがないようなので以下から最新のnkfをダウンロードしてきます。
当然ですがUTF-8対応のnkfをインストールします。
http://www01.tcp-ip.or.jp/~furukawa/nkf_utf8/
ダウンロードしたファイルnkf205.tar.gzを解凍してインストールしましょう。
# tar zxvf nkf205.tar.gz
# cd nkf205
# make
# make test
エラーが出なければ出来た実行ファイルとマニュアルをコピーします。
# cp nkf /usr/local/bin
# cp nkf.1 /usr/share/man/man1/
これでOK。