sudo hostnamectl set-hostname HOSTNAME to set a new hostname for your machine. This command does all of the steps in one go and takes the worry out of this task. Just close the terminal after entering this command and reopen it and the new hostname will be visible.
Here I am setting a new hostname of Yog-Sothoth.
sudo hostnamectl set-hostname "Yog-Sothoth"
This will take effect immediately.
Use this command to view the new hostname.
hostnamectl status --pretty
This command is available when you are booted using Systemd and may not work on Debian. Read more here: http://wiki.gentoo.org/wiki/Systemd#Hostname.