As of 07-11-13 GeoDjango should be installed as follow:

sudo apt-get install postgresql python-psycopg2 build-essential flex libpq-dev postgresql-server-dev-8.2 swig
sudo apt-get install ipython  #not mandatory but usefull when using django manage.py shell
sudo apt-get install subversion #to get geo django trunk

Django wiki recommend the use of geos 3 that does not exists as an Ubuntu pkg let's compile it:
Note that this will install all this things in /usr/local/... with no clean way to uninstall it except rm.

wget http://geos.refractions.net/geos-3.0.0rc4.tar.bz2
tar jxf geos-3.0.0rc4.tar.bz2 
cd geos-3.0.0rc4
./configure 
make
sudo make install
cd ..

wget ftp://ftp.remotesensing.org/proj/proj-4.5.0.tar.gz
wget ftp://ftp.remotesensing.org/proj/proj-datumgrid-1.3.tar.gz
tar zxf proj-4.5.0.tar.gz 
cd proj-4.5.0/nad/
tar zxf ../../proj-datumgrid-1.3.tar.gz 
cd ..
./configure
make
sudo make install
cd ..

Postgis 1.3.1 must be compiled with the geos 3 as dependencies that's why we don't want to use the postgis ubuntu pkg

wget http://postgis.refractions.net/download/postgis-1.3.1.tar.gz
tar zxf postgis-1.3.1.tar.gz 
cd postgis-1.3.1/
./configure --with-geos --with-proj
make
sudo make install
cd ..

su - postgresql
createuser yourdbuser
createdb -O yourdbuser yourdb
createlang plpgsql yourdb
psql -d yourdb -f /usr/share/lwpostgis.sql
psql -d yourdb -f /usr/share/spatial_ref_sys.sql 
psql yourdb
yourdb=# GRANT SELECT, UPDATE, INSERT, DELETE ON geometry_columns TO yourdbuser;
yourdb=# GRANT SELECT ON spatial_ref_sys TO yourdbuser;
exit

wget http://download.osgeo.org/gdal/gdal-1.4.3.tar.gz
tar zxf gdal-1.4.3.tar.gz 
cd gdal-1.4.3/
./configure --with-geos
make
make install

You can now remove all the compilation directories, then get GIS Django branch with subversion:

svn co http://code.djangoproject.com/svn/django/branches/gis django_gis
export PYTHONPATH=$PYTHONPATH:/thepathwhereyousvnco/django_gis

Then follow the normal Django usage.