gnuplotで日本語を使う方法 on fedora10

set terminal postscript eps enhanced "Ryumin-Light-UniJIS-UTF8-H"

ってやれば多分いけると思います。