Para para começar vamos logo dizendo que LAMP é uma abreviação para os seguintes software Linux, Apache, MySQL e PHP que juntos formam o ambiente que necessitamos para desenvolver e hospedar nossos sites.

1. Instalar o MySQL

sudo aptitude install mysql-server mysql-client

Durante a instalação a senha do usuário root do MySQL será pedida.

2. Instalar o Apache 2

sudo aptitude install apache2

Depois instalado verifique se esta funcionando acesse http://localhost se aparecer um “It works!” está funcionando.

3. Instalar o PHP 5

sudo aptitude install php5 libapache2-mod-php5

Não se esqueça de instalar também o modulo PHP do MySQL.

apt-get install php5-mysql

Bom já temos o básico agora. É só reiniciar o Apache que deve estar tudo funcionando.

/etc/init.d/apache2 restart

4. Habilitando o mod_rewrite

O mod_rewrite é utilizado por vários CMS, Framework e etc. Então é sempre uma boa ideia habilitá-lo. Para você que não sabe o que é o mod_rewrite veja o post sobre URLs amigáveis

a2enmod rewrite

E altere o seguinte trecho de código no arquivo /etc/apache2/sites-enabled/000-default:

<Directory /var/www/>
        Options Indexes FollowSymLinks MultiViews
        AllowOverride None
        Order allow,deny
        allow from all
</Directory>

por: 

<Directory /var/www/>
        Options Indexes FollowSymLinks MultiViews
        AllowOverride All
        Order allow,deny
        allow from all
</Directory>

Agora reinicie o Apache e tome uma cerveja! T++

Para quem precisar usar o PostgreSQL (LAPP?): 

apt-get install php5-pgsql