O mysql-server é um metapacote que depende da última versão do mysql-server, então não precisa ser instalado. Abra o terminal e digite:
sudo apt-get update
sudo apt-get install aptitude
sudo aptitude install mysql-server-5.5 mysql-server-core-5.5
$ sudo apt-get install mysql-server
[sudo] password for user:
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package mysql-server
Estou usando o Ubuntu 14.04.
O mysql-server é um metapacote que depende da última versão do mysql-server, então não precisa ser instalado. Abra o terminal e digite:
sudo apt-get update
sudo apt-get install aptitude
sudo aptitude install mysql-server-5.5 mysql-server-core-5.5
Você deve primeiro verificar se o pacote que você está procurando existe ao abrir o terminal e digitar:
apt search <your package name>
Selecione o pacote que você deseja instalar digitando
sudo apt-get install <the package name you found after searching>
Você também pode fazer isso no aplicativo do gerenciador de pacotes sinápticos.