El proceso es bastante sencillo y rápido desde la consola.

Primero instalamos Mysql con el comando

apt-get install apache2
apt-get install php5
apt-get install php5-mysql
apt-get install libapache2-mod-auth-mysql
sudo apt-get install mysql-server-5.1

Luego Apache con el comando

sudo apt-get install apache2

Luego PHP con el comando

sudo apt-get install php5

Finalmente conectamos Mysql con Apache y PHP  con los comandos

sudo apt-get install php5-mysql
sudo apt-get install libapache2-mod-auth-mysql

Para asegurarnos reiniciamos Mysql y Apache con los comandos

sudo /etc/init.d/apache2 restart
sudo /etc/init.d/mysql restart

Para verificar que todo quedo bien instalado pondremos un archivo llamado info.php en la carperta /var/www/ con el siguiente contenido

<?
phpinfo();
?>

Abrimos el navegador de internet y navegamos la URL http://127.0.0.1/info.php y deberiamos ver algo asi

apache_php

en particular para verificar que PHP tenga soporte para Mysql en la zona media tenemos que encontrar un bloque de Mysql parecido al de la imagen que se ve a continuación

apache_php_msqyl