mysql é o programa do cliente. Você precisa instalar o servidor mysql ao qual você pode se conectar.
sudo apt-get install mysql-server-5.5
Durante a instalação, você será perguntado pela senha do root que será atribuída ao usuário root do mysql.
Então você precisa iniciar o serviço mysqld
sudo service mysqld start
Ou
sudo /etc/init.d/mysqld start
Ou
sudo service mysql start
(Todas as três linhas fazem o mesmo)
Finalmente, você pode se conectar
mysql -uroot -p