If you don't mind using the non-latest versions, you can get up and running real-fast-like:

First, ensure you have some base packages installed on your Ubuntu system:

• If you don't want to use the CD as a source for files, comment out the CDROM line (2nd or 3rd line) in /etc/apt/sources
  • New to Ubuntu? Unclear on how to do this? Check out the UbuntuStarter page.
• Install latest updates from the repository

  sudo apt-get update
  sudo apt-get upgrade
  

And now, let's install mapserver, postgis, and a few other goodies in a these two simple steps:

sudo sudo apt-get install postgresql-8.3  postgresql-server-dev-8.3 postgis
sudo apt-get install cgi-mapserver mapserver-bin python-gdal python-mapscript

Optional:

• Install the apache webserver, and an ssh client so you can log in remotely

   sudo apt-get install ssh apache2
  

• Want more? Try searching with aptitude. Say you'd like to grab the full gdal/ogr utilities, try:

  aptitude search gdal
  # This returns a list of options. One of the listings you'll see is "gdal-bin"
  sudo apt-get install gdal-bin
  

• Create a PostGIS database

  #login as postgres
  sudo su postgres
  #create database stuff
  createdb test_db
  createlang plpgsql test_db
  psql -f /usr/share/postgresql-8.3-postgis/lwpostgis.sql -d test_db
  psql -f /usr/share/postgresql-8.3-postgis/spatial_ref_sys.sql -d test_db
  #logout of postgres user
  exit
  

You're done installing!

To learn about a few more goodies to install see Ubuntu Desktop installs.

To begin using what you have see these base examples.