Linux は良く分かりませんので、一般的なヒントを。

alamo> set term x11では
alamo> gnuplot> set title "漢字とひらがな" font "Ryumin-Light-UniJIS-UTF8-H,18"
alamo> はOKだけど
alamo> gnuplot> set title "漢字とひらがな" font "GothicBBB-Medium-UniJIS-UTF8-H,18"
alamo> は文字化けします。

x11 では、

Ryumin-Light-* ==> -*-mincho-medium-[slant]-*--[size]-*
GothicBBB-Medium-* ==> -*-gothic-bold-[slant]-*--[size]-*

が使われています。xfontsel で確認すると何かわかるかもしれません。

alamo> そして前者の場合でも、term postscript epsとして書き出すととやはり文字化けしています。
alamo> set term postscript eps "Ryumin-Light-UniJIS-UTF8-H"としてもダメでした。

gnuplot は、単に指定されたフォント名を eps に書き出すだけなので、gnuplot
の問題というよりは表示する方の問題だと思います。この eps の「文字化け」は、
どうやって確認したのでしょう。

alamo> またpngの場合は、set term png medium font "/usr/...../ipag-mona.ttf,14"
alamo> とすれば、ちきんと日本語が表示されます。

これは eps や x11 の出力方法とは仕組みが違い、日本語化「されていない」
gdlib と Unicode エンコーディングに対応している ttf ならば、UTF-8 で正
常に表示されるはずです。

alamo> CIDFnmapには、
alamo> /IPAMonaGothic-Regular (/usr/...../ipag-mona.ttf) /Adobe-Japan1-Unicode ;
alamo> /Ryumin-Light /IPAMonaPMincho-Regular ;
alamo> /GothicBBB-Medium /IPAMonaGothic-Regular ;
alamo> などとかかれています。

うちは、ipam.ttf, ipag.ttf で同様の設定で試してみましたが、うまく行き
ました:

CIDFnmap:
/TESTMJP (/usr/local/share/fonts/ttf/ipam.ttf) /Adobe-Japan1-Unicode ;
/TESTGJP (/usr/local/share/fonts/ttf/ipag.ttf) /Adobe-Japan1-Unicode ;
% 以下でも OK
% /TESTMJP (/usr/local/share/fonts/ttf/ipam.ttf) ;
% /TESTGJP (/usr/local/share/fonts/ttf/ipag.ttf) ;

gnuplot スクリプト:
set term post eps
set out "test.eps"
set title "漢字とひらがな" font "TESTMJP-UniJIS-UTF8-H"
set xlabel "漢字とひらがな" font "TESTGJP-UniJIS-UTF8-H"
plot sin(x)
set out

テストした Ghostscript, gnuplot のバージョンは以下の通りです:

Ghostscript: 7.07
gnuplot-4.2.0

〔ツリー構成〕

【1813】 epsへの日本語出力が文字化けする 2008/4/6(日)22:58 alamo (886) ≪

┣【1814】 re(1):epsへの日本語出力が文字化けする 2008/4/7(月)09:30 竹の (1995)

┣【1816】 re(2):epsへの日本語出力が文字化けする 2008/4/7(月)19:20 alamo (463)

┣【1818】 re(3):epsへの日本語出力が文字化けする 2008/4/8(火)09:34 竹の (1491)

┣【1819】 re(4):epsへの日本語出力が文字化けする 2008/4/8(火)11:25 alamo (538)

┣【1820】 re(5):epsへの日本語出力が文字化けする 2008/4/8(火)11:57 竹の (1663)

┣【1821】 re(6):epsへの日本語出力が文字化けする 2008/4/8(火)20:23 alamo (943)

┣【1822】 re(6):epsへの日本語出力が文字化けする 2008/4/9(水)00:01 alamo (556)

┣【1815】 re(1):epsへの日本語出力が文字化けする 2008/4/7(月)09:47 松岡 (511)

┣【1817】 re(2):epsへの日本語出力が文字化けする 2008/4/7(月)19:22 alamo (317)