all the above solutions are correct but I would try with

sudo apt-get remove --purge mysql*
sudo apt-get autoremove
sudo apt-get autoclean

This will uninstall all mysql related packages.

This will remove mysql 5.6 from ubuntu 15.04

sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
sudo rm -rf /var/lib/mysql
sudo rm -rf /etc/mysql

First you need to stop your mysql server from service.

sudo service mysql stop

Then You can use purge command to uninstall

sudo apt-get purge mysql-server mysql-client

Note: the above based on your package list. I have installed both server and client. This will for your convineient

I don't use Ubuntu much but what I think you should try is what I did.

I first typed this in command line : sudo apt-get remove --purge mysql-server mysql-client mysql-common,

then followed with this below : sudo apt-get autoremove

and finally typed this : sudo apt-get autoclean.

I found that it was removed.

I forgot the mysql root password and needed to reset.
I tried this http://www.rackspace.com/knowledge_center/article/mysql-resetting-a-lost-mysql-root-password and didn't work because it kept saying can't write logs or similar.
Now my solution was to completely remove mysql from Ubuntu13.10 and fresh installation.

sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo rm -rf /var/lib/mysql

I had to run the last commandline, because Ubuntu sometimes keeps some libs even you try purge them all.
Now install mysql server and client

sudo apt-get install mysql-client mysql-server

When I tried sudo apt-get purge mysql* it didn't work.

Purged mysql5 with:

sudo apt-get purge mysql-*

Then for cleaning up:

sudo apt-get autoremove
sudo apt-get autoclean

Completly uninstall mysql:

sudo -i
service mysql stop
killall -KILL mysql mysqld_safe mysqld
apt-get --yes purge mysql*
apt-get --yes autoremove --purge
apt-get autoclean
deluser --remove-home mysql
delgroup mysql
rm -rf /etc/apparmor.d/abstractions/mysql /etc/apparmor.d/cache/usr.sbin.mysqld /etc/mysql /var/lib/mysql /var/log/mysql* /var/log/upstart/mysql.log* /var/run/mysqld ~/.mysql_history
updatedb

Based on this answer and many others...

Try this, It will fully wipeout out every single file of MySQL from your system:

sudo service mysql stop #or mysqld
sudo killall -9 mysql
sudo killall -9 mysqld
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
sudo deluser -f mysql
sudo rm -rf /var/lib/mysql
sudo apt-get purge mysql-server-core-5.7
sudo apt-get purge mysql-client-core-5.7
sudo rm -rf /var/log/mysql
sudo rm -rf /etc/mysql