Apt-get remove is not always enough to remove a package completely. If you try to remove in example the mysql-server package with just apt-get remove, the settings and lot of dependencies will still be left. We will need to purge and clean up. Here is a short desription on how to perform a complete removal of mysql-server with settings and everything.
First you need to run the remove –purge command.
apt-get remove –purge mysql\*
Next step is probably not recommended by debian.org as it will increase their bandwith (unless you run your own apt-get cache server, which I recommend everyone to do). That is to clean the package cache.
The last step is often forgotten, included by my self. That is to update the file database. Else references to all the deleted files will still be present.
Thats it, and your mysql server is now completely gone.