RHEL（またはCentOS)の3からは、nkfがなくなってます、ちょっといれといてくれればいいのにって感じですが、代わりの方法としてiconvで以下のようにすれば変換できます。
iconv -f EUC-JP -t UTF-8 変換元 > 変換先
とはいいつつ面倒なので、コンパイルしていれちゃいました。
nkf Network Kanji Filter(SOURCE FORGE JP)
しかし、最近は、RPMでのみの管理してるので、開発環境はいれてないから、yum groupinstall “Development Tools”とかして、しこたまインストールしないといけない罠が。。orz
ついでに、RHEL4からは標準の日本語環境がUTF-8になってしまってるので、ターミナルの設定変更や（これは変えればいいだけだけど）、他のEUC-JPのマシンからSSHとかでログインしたときに文字化けしていや～んなので、ロケールを変える方法
/.bashrc export LANG=ja_JP.eucJP export LC_ALL=ja_JP.eucJP
2007/04/23追記>
CentOS5ではnkfが復活したようです。
$ rpm -qa | grep nkf nkf-2.07-1.1.fc6