How do I completely remove Samba?

So, for the server, from the Terminal:

sudo apt-get remove --purge samba
sudo apt-get install samba

But, if you are having client problems, it would be more like:

sudo apt-get remove --purge smbclient libsmbclient
sudo apt-get install smbclient libsmbclient

Update:

Note that this answer only applies to Ubuntu 11.10! More recent Ubuntus will probably remove useful software with the apt remove command, so be sure to check what is being removed and if needed "cherrypick" packages in synaptic or similar.

A easier way to remove Samba that is simpler and cleaner.

sudo apt-get autoremove samba samba-common

This step uses the autoremove to remove the package.

sudo apt-get purge samba samba-common

This step cleans any configuration file you may have