Bom, vai parecer um pouco, ou melhor, bastante duplicados, mas vou ensinar os passos para instalar o LAMP no ubuntu. Utilizarei a distro ubuntu 9.10.

Instalando o Apache
No terminal, execute:

sudo apt-get install apache2

Com isso você já terá o apache rodando.
Teste: http://localhost/

Instalando o PHP

sudo apt-get install php5 libapache2-mod-php5
sudo /etc/init.d/apache2 restart

Instalando o MySQL

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

E por fim, o que não poderia faltar: habilitando o Mod_Rewrite do Apache

sudo a2enmod rewrite
sudo sed -i '/<Directory\s\/var\/www\/>/{N;N;s/none$/All/i}' /etc/apache2/sites-enabled/000-d
sudo apache2ctl restart