私は，環境が異なるので答えられるかどうか分かりませんが。
gnuplotとのバージョンやもう少し具体的な操作の例などを
示していただかないと回答がつきません。

例えば
gnuplot version 4.0(windows)で
gnuplot> set term post
gnuplot> set out 'test.ps'
gnuplot> set title '日本語'
gnuplot> plot sin(x)
gnuplot> set out
で作製したpostscriptファイルをpostscript viewerでみると
日本語が文字化けします。
OSはwin xp pro sp2です。
など

〔ツリー構成〕

【585】 文字化け 2004/12/10(金)17:36 まろん (232) ≪

┣【587】 re(1):文字化け 2004/12/10(金)17:59 まろん (165)

┣【588】 re(1):文字化け 2004/12/10(金)18:17 松岡 (418)

┣【589】 re(1):文字化け 2004/12/10(金)18:29 まろん (205)

┣【590】 re(2):文字化け 2004/12/10(金)18:40 松岡 (178)

┣【591】 re(3):文字化け 2004/12/10(金)20:21 松岡 (164)

┣【593】 re(2):文字化け 2004/12/10(金)21:46 竹の (613)

┣【594】 re(3):文字化け 2004/12/10(金)22:05 まろん (254)

┣【595】 re(4):文字化け 2004/12/11(土)12:58 松岡 (777)

┣【596】 re(5):文字化け 2004/12/11(土)15:32 竹の (893)

┣【599】 re(6):文字化け 2004/12/11(土)16:24 松岡 (532)

┣【592】 re(1):文字化け 2004/12/10(金)21:39 まろん (136)