Bueno la forma mas sencilla de hacerlo es por Synaptic un par de clicks y listo y pues esta también por consola, que también es sencilla. A mi modo de ver. Pero en fin... Voy a explicar como hacerlo por ambos métodos para que no quede ninguna duda.
Antes de cualquiera de las dos formas, tenemos que agregar o habilitar los repositorios Universe y Multiverse en la lista de repositorios de nuestro sistema.
$ sudo gedit /etc/apt/sources.list
y quitamos el comentario # a las lineas de universe y multiverse
guardamos y luego damos
$ sudo aptitude update
con esto ya tenemos los repositorios activados ahora si vamos a lo que vinimos.
Método gráfico

Aquí buscamos y seleccionamos los siguientes paquetes:
apache2
php5
mysql-server
mysql-client
php5-mysql
php5

luego cuando damos en aplicar, este nos dice que necesita otros paquetes y le decimos que los agregue y esperamos a que termine de instalarlos y listo.
Método consola
Para este desde nuestra consola damos lo siguiente:
Instalamos Mysql
$ sudo aptitude mysql-server-5.0
$ sudo aptitude mysql-client-5.0
Instalamos apache
$ sudo aptitude apache2
Instalamos php
$ sudo aptitude php5
y para el soporte entre mysql y apache y php
$ sudo aptitude php5-mysql
luego reiniciamos el servidor apache y todo debe quedar listo
$ sudo /etc/init.d/apache2 restart
con esto ya tendremos lo necesario instalado.
para probar nuestra instalación en el navegador podemos ir a http://localhost y si todo salio bien debe correr el apache.
Nota
Si tenemos algún problema con la codificación de caracteres, cosa que a mi me paso, pueden hacer lo siguiente:
ir a el archivo de configuración de apache
$ sudo gedit /etc/apache2/apache2.conf
y buscamos donde se encuentra esta linea y le quitamos el comentario #
#addDefaultChatset ISO-8859-1
y reiniciamos el servidor apache con esto ya debe funcionar correctamente la codificación de caracteres.