Além de depenar na fonte do Repositório. Você pode tentar seguir
sudo apt-get update && sudo apt-get upgrade
Em seguida, procure o pacote usando o apt-cache.
sudo apt-cache search mysql | grep mysql | more
Você terá alguns resultados e poderá escolher um adequado para você. Você pode precisar do cliente ou do servidor (depende das suas necessidades). O resultado é como abaixo:
mysql-server - MySQL database server (metapackage depending on the latest version)
mysql-server-5.5 - MySQL database server binaries and system database setup
mysql-client - MySQL database client (metapackage depending on the latest version)
mysql-server - MySQL database server (metapackage depending on the latest version)
mysql-client-5.5 - MySQL database client binaries
Depois de descobrir qual versão do sql está disponível. Você pode instalá-lo com o apt-get.
sudo apt-get install mysql-server mysql-client
Espero que isso ajude. Alos esta é a página oficial da Comunidade Mysql para baixar o MySQL Server para diferentes plataformas.