竹のさんの説明の通りですが，1点．次の指定でepsが出来たとおっしゃいましたが，
日本語も正常に表示されたという意味でしょうか？
漢字コードを拡張ユニックス(EUC-H)で指定しているので，
エディタの保存漢字コードも拡張ユニックスでなければならないはずですが．

set terminal postscript eps enhanced color 'GothicBBB-Medium-EUC-H' 20

MS-Windowsならば90ms-RKSJ-Hを指示してShift-JISで保存するか，
あるいはUniJIS-UTF8-Hを指示してUTF-8で保存しなければなりません．
もちろんEUC-Hを指示して，EUC-JPで保存してもかまいません．
漢字コードを統一してください．

XnViewというツールを使ってみました．私はLinuxですが，euc-jpの範囲内では
正常に変換できました．もっともLinuxではxvやImageMagick，Gimpが使える
(正確にはバックエンドのghostscriptが正常にインストールされている)ので
何も不便はないですが．

〔ツリー構成〕

【2118】 pngへの出力で日本語が文字化けする 2009/11/1(日)17:33 OHTA (2000) ≪

┣【2119】 re(1):pngへの出力で日本語が文字化けする 2009/11/2(月)10:05 竹の (1564)

┣【2120】 re(2):pngへの出力で日本語が文字化けする 2009/11/2(月)22:25 松田七美男 (771)

┣【2121】 re(3):pngへの出力で日本語が文字化けする 2009/11/4(水)11:01 松岡 (1331)

┣【2128】 re(4):pngへの出力で日本語が文字化けする 2009/11/6(金)00:21 松岡 (1002)

┣【2130】 re(3):pngへの出力で日本語が文字化けする 2009/11/8(日)15:24 OHTA (2470)

┣【2134】 re(4):pngへの出力で日本語が文字化けする 2009/11/8(日)18:17 松田七美男 (666)

┣【2140】 re(5):pngへの出力で日本語が文字化けする 2009/11/9(月)09:51 竹の (546)

┣【2138】 re(4):pngへの出力で日本語が文字化けする 2009/11/9(月)09:28 竹の (704)

┣【2145】 re(2):pngへの出力で日本語が文字化けする 2009/11/9(月)14:19 松岡 (326)

┣【2122】 re(1):pngへの出力で日本語が文字化けする 2009/11/4(水)16:30 松岡 (1228)

┣【2124】 re(2):pngへの出力で日本語が文字化けする 2009/11/5(木)15:08 kakuto (233)

┣【2125】 re(3):pngへの出力で日本語が文字化けする 2009/11/5(木)15:16 kakuto (369)

┣【2126】 re(3):pngへの出力で日本語が文字化けする 2009/11/5(木)18:46 松岡 (804)

┣【2123】 re(1):pngへの出力で日本語が文字化けする 2009/11/4(水)17:43 竹の (350)

┣【2127】 re(2):pngへの出力で日本語が文字化けする 2009/11/5(木)23:12 OHTA (3029)

┣【2129】 re(3):pngへの出力で日本語が文字化けする 2009/11/6(金)13:13 竹の (1747)

┣【2131】 pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/8(日)15:27 OHTA (2284)

┣【2132】 re(1):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/8(日)17:43 松岡 (540)

┣【2133】 re(2):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/8(日)18:11 松岡 (764)

┣【2135】 re(3):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/8(日)18:24 松岡 (607)

┣【2137】 re(3):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)09:21 竹の (1141)

┣【2141】 re(4):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)11:52 松岡 (1647)

┣【2142】 re(5):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)13:03 竹の (732)

┣【2144】 re(6):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)13:30 松岡 (1044)

┣【2143】 re(4):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)13:06 松岡 (1485)

┣【2139】 re(1):pltファイルをロードして日本語のpng画像を出力する方法例 2009/11/9(月)09:34 竹の (545)

┣【2146】 re(1):pngへの出力で日本語が文字化けする（utfなしで日本語出せます。） 2009/11/9(月)16:17 松岡 (1538)