The X2Go project is a fairly efficient way to provide a graphical remote access to a Linux box. It is based on the excellent NoMachine free libraries, which is the technology behind the NX server and the FreeNX project, which seems not developped anymore.
A client will then only need a SSH access to the server to get a full featured graphical remote desktop.
Available for many Linux flavours, MS Windows and Mac OS X, the installation on a Debian client or server is really easy and straightforward, thanks to the packaging effort done by X2Go, and all the relevant information can be found on the wiki of the X2Go project.