Start by changing the hostname in /etc/hostname.
$ echo "your_new_hostname" | sudo tee /etc/hostname
You will also need to replace the entries in /etc/hosts that refers to the old hostname.
$ sudo sed -i 's/old_hostname/new_hostname/g' /etc/hosts
The changes you have made will not take effect before you reboot.