If you want the newest version of Octave (3.8 as of the time of writing) you will need to compile it yourself.
Do
sudo apt-get build-dep octave sudo apt-get install libqscintilla2-9 libqscintilla2-dev wget ftp://ftp.gnu.org/gnu/octave/octave-3.8.0.tar.bz2 tar -xvf octave-3.8.0.tar.bz2 cd octave-3.8.0 ./configure make make check sudo make install
when this is done Octave should work for you. Keep an eye out for warnings though. This was tested on Ubuntu 13.04 64 bit. If you use Debian you will need libqscintilla2-8 instead of 9. I am actually not sure if you only need the dev package. On Debian you will also need to install libxft2-dev since this is not installed by default.
To run Octave with the GUI enabled run
octave –force-gui
this enables the GUI. The GUI is still in beta though so it might be a bit rough.