How do you completely remove ubuntu-desktop along with all installed packages with it?

Even better than just doing remove, you can use purge and then autoremove.

sudo apt-get purge ubuntu-desktop
sudo apt-get autoremove

Purge option according to the man page for apt-get:

**purge**
purge is identical to remove except that packages are
removed and purged (any configuration files are deleted too).

First do

apt-get remove ubuntu-desktop
apt-get autoremove

Then do the

sudo apt-get remove nautilus nautilus-* gnome-power-manager gnome-screensaver gnome-termina* gnome-pane* gnome-applet* gnome-bluetooth gnome-desktop* gnome-sessio* gnome-user* gnome-shell-common zeitgeist-core libzeitgeist* gnome-control-center gnome-screenshot && sudo apt-get autoremove

to end up with a completely GUI'less environment. This worked for me to remove the ubuntu-desktop I had installed on my Ubuntu Server

Remove the package and the auto-remove the installed dependencies. As root:

apt-get remove ubuntu-desktop
apt-get autoremove

See also apt-get(8) manual page for the autoremove argument.

autoremove (and the auto-remove alias since 1.1)

autoremove is used to remove packages that were automatically installed to satisfy dependencies for other packages and are now no longer needed.