Gnuplot is a nice program for 2D and 3D plotting.
However, its builtin-readline library is somehow limited and does not provide
many of the nice features of
GNU-readline.
Somehow
the GPL is not compatible with gnuplots license, which leads to the fact that
you are not allowed to distribute binaries of gnuplot with
gnu-readline support compiled in. Thats why the debian/ubuntu package comes
without it.

I am far from being an expert in FLOSS
licenses, but I think that you are allowed to compile gnuplot for yourself
using GNU-readline and it is very easy.

It is also desirable to install it within a deb-package so that you can profit
from the merits of package management, so I had a look at the
debian manual
Which gives a good description on how to build binary packages from source packages.

First we let apt install all the dependencies for compiling gnuplot

sudo apt-get build-dep gnuplot-x11

we also nead the development files for gnu-readline and the fakeroot
and dpkg-dev packages to build the debian packages later

sudo aptitude install libreadline5-dev fakeroot dpkg-dev devscripts

Now that we are all set up we let apt get the sources

apt-get source gnuplot-x11

let dpkg apply the debian/ubuntu patches:

dpkg-source -x gnuplot_4.2.0-3.dsc

note: 4.2.0-3 is the current version for ubuntu gutsy, of course you have to
put in your own version.

Go to the gnuplot directory and open debian/rules in your favorite text
editor

cd gnuplot-4.2.0
vi debian/rules

in the config.status-section you find a line saying:

--without-gnu-readline --without-lasergnu \

change it to

--with-readline=gnu --without-lasergnu \

of course you can adjust some other options to your needs, they are listed
in the INSTALL file.
In order for apt not to want to upgrade the package all the time, we need to make
an entry in the changelog (thats why we installed devscripts earlier):

dch -i

This will open your $EDITOR, so you can just add something (its only for you, so it
does not matter what you write).
Exit your $EDITOR and build the packages

dpkg-buildpackage -rfakeroot -b

If everything went fine, there should be some packages in the upper level directory,
you can install them with

sudo dpkg -i gnuplot-x11_4.2.0-3_i386.deb \ 
      gnuplot-nox_4.2.0-3_i386.deb \
      gnuplot-doc_4.2.0-3_all.deb

And you are good to go! Remember that you are not allowed to distribute
the binaries. Another downside is that you have to recompile every time there is
an update of gnuplot in the repositories (though this should not happen too often).