Esta busca somente a revisão 5.1:
sudo apt-get install mysql-server
mas a versão mais recente do servidor da comunidade é 5.5.9
apt-get é uma ferramenta específica para distribuições linux baseadas no debian, e só fará o download de pacotes de locais especificados em /etc/apt/source.lst.
Para atualizar para o 5.5, você precisará encontrar um repositório com as compilações mais recentes e adicioná-lo ao seu sources.lst, ou você terá que baixar manualmente e instalar um dos pacotes do site do mysql.
Você pode baixar o pacote RPM da página de download do MySQL e convertê-lo usando o alien. Então você pode instalar o pacote .deb usando "dpkg -i". Baixe o pacote RPM (64 bits ou 32 bits) e execute os seguintes comandos:
sudo apt-get install alien fakeroot
fakeroot alien MySQL-devel-5.5.9-1.linux2.6.i386.rpm
dpkg -i mysql-devel_5.5.9-2_i386.deb
Isso é melhor do que instalar a partir do código-fonte, pois agora os arquivos são rastreados pelo dpkg (backend para apt, aptitude e outros gerenciadores de pacotes no Ubuntu).
Não há PPA oferecendo o mais recente servidor mysql para o Ubuntu, pelo menos eu não consegui encontrá-lo. 5.1 é considerado como mysql estável, enquanto 5.5 é "versão upstream". Haverá pacotes do Ubuntu, mas boa pergunta é quando.