Estou usando o Ubuntu (baseado no Debian) e segui etapas muito semelhantes com sucesso. No entanto eu baixei o pacote debian, não o binário: link
então eu corri:
sudo apt-get install libaio1
sudo groupadd mysql
sudo useradd -r -g mysql mysql
wget -O mysql-5.6.11-debian6.0-x86_64.deb \
http://downloads.mysql.com/archives/mysql-5.6/mysql-5.6.11-debian6.0-x86_64.deb
sudo dpkg -i mysql-5.6.11-debian6.0-x86_64.deb
cd /usr/local
sudo ln -s /opt/mysql/server-5.6 mysql
cd mysql
sudo scripts/mysql_install_db --user=mysql
sudo chown -R root .
sudo chown -R mysql data
sudo cp support-files/mysql.server /etc/init.d/mysql
sudo service mysql start
sudo ./bin/mysql_secure_installation
O último passo é opcional.
EDITAR
Acabei de fazer o download do .tar.gz
que você usou e essas são as origens. Então basicamente você precisa instalar o CMAKE e construir o MySQL sozinho. Eu fiz isso duas semanas atrás e não é tão difícil (se você já construiu coisas no linux antes :)), mas duvido que você precise passar por esse fardo. Você só precisa descobrir quais erros são relatados com a instalação do .deb e compartilhá-los aqui para que possamos ajudar.
UPDATE
Para o problema que inicia o MySQL, no arquivo /etc/init.d/mysql (copiado de /opt/mysql/server-5.6/support-files/mysql.server nas etapas acima) altere as linhas 48-49 o vazio
basedir=
datadir=
para
basedir=/usr/local/mysql
datadir=/usr/local/mysql/data
(ou qualquer outro caminho necessário)
Note que você pode precisar adicionar as seções [client] e [mysqld] do seu /etc/my.cnf (este pacote debian espera este arquivo em / etc OU /opt/mysql/server-5.6 não / etc / mysql)
socket = /var/run/mysqld/mysqld.sock
Ou você pode ter problemas para se conectar a partir do PHP ou outra linguagem de programação.