Primero hay que instalar MySQL. En debian es muy sencillo, basta con teclear el siguiente comando (logueado como root):
aptitude install mysql-server
en el proceso pedirá una contraseña para el usuario root que administra la base de datos.
aptitude install mysql-server