I've still to find the ideal software
Gnuplot - my favouried since scriptable, quick and using postscript enhanced or mpost it is also quite flexible.
QtiPlot - a real Origin clone which works under Linux and Windows, looks quite promissing, but has still to go some way. It has a fork named SciDAVis.
LabPlot - seems to be actively developed and quite powerful, but I don't like the graphical interface.
SciGraphica - dead since 2001, but seems to be reviving in the last months of 2004; I never tested it.
Grace (decent of ACE/gr = Xmgr) - in principle a nicely working plot program, but I never liked it since I failed to get used to the user interface.
Origin - a rather expensive Windows program; depending on the its version and the one of WINE/CrossOver Office it might work quite well; I tried Origin 7.5 Demo, but I couldn't install it, Origin 6.0 on the other hand seemes to work reasonable well. Since it is expensive and not scriptable, I never really used it, but for most experimentalists I've met it is really indispensible
Igor - another Windows plot program, I've never used or tested; some swear by it as others do for Origins. No idea whether it runs using WINE
Others: Mathematica, Maple and other mathematical tools have ploting functionalites; special purpose or small (?) programs exists as well (KPlot, XGraph, XGRAPH, kmPlot, OpenDX etc.). In addition, several libraries allow the direct creation of plots, e.g. CERN's Root.