What I now do is to use gnuplot terminal "postscript enhanced" and print to ".ps" file. Then I use the tool ps2eps, which generates a better bounding box. The call is
ps2eps -f -B -l -R + data.ps
-f: forces overwrite of existing eps files, -B recalculates bounding box, -l adds a bit to it, so it does not terminate on the labels, -R + sometimes rotation is required. No output file is required.
Then, the .eps file is opened in preview and saved to PDF. If using "convert" again PDF will have a too large white space margin, probably there are some options to adjust this, havent found them yet.
Another option (Credits: Janus)