Primeiramente deveremos fazer o download do mysql-server,

Se você utilizar o Debian, utilize/adicione o repositório abaixo,

deb http://mirror.ucpel.tche.br/debian etch main

Caso você utilize o Ubuntu, utilize/adicione o repositório abaixo,

deb http://debian.ucpel.tche.br/apt-cacher/br.archive.ubuntu.com/ubuntu/ hardy main restricted

Após ter feito isto, vamos ao que interessa,

apt-get install mysql-server

No Ubuntu, durante a instalação ele te pedirá uma senha para o usuário root, porém no Debian ele não pede, então mostrarei o que deve ser feito,

Após ter instalado o MySQL, você deverá digitar a senha manualmente, abaixo mostrarei os comandos necessários,

mysql_install_db

/usr/bin/mysqladmin -u root password 'new-password'

Onde 'new-password' é o local onde tu deves colocar a senha, exemplo de senha: 'senhaqui'

Vamos testar o acesso ao MySQL,

mysql -u root -p

Digite a senha:

A saída no Ubuntu deve ser esta:

guilherme@Gui-desk:~$ mysql -u root -p
Enter password: 
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 52
Server version: 5.0.51a-3ubuntu5.1 (Ubuntu)
Type 'help;' or '\h' for help. Type '\c' to clear the buffer.
mysql> 

e no Debian, a saída deve ser esta:

guilherme@master:~$ mysql -u root -p
Enter password: 
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 165
Server version: 5.0.32-Debian_7etch6-log Debian etch distribution
Type 'help;' or '\h' for help. Type '\c' to clear the buffer.
mysql> 

Espero ter ajudado,

[]'s
Guilherme