Using the terminal,
sudo nano /etc/hostname
Using Terminal and graphical editor. (this requires Ubuntu / Desktop desktop edition)
[ Also, this method requires gksu which can be installed using
sudo apt-get -y install gksu
]
gksudo gedit /etc/hostname
Change the hostname to what you desire and reboot.
To change the hostname for the current session without making permanent change you can also use
sudo hostname mnewhost.localdomain