As described at it’s straight forward:
sudo /bin/hostname mynewhostname
Supplying the path to the binary is for security reasons, I guess, to make sure we have the right bin (eventhough it could have been replaced there, too…).
But the people at debianadmin.com forgot to mention in order to avoid “hostname: Unknown Host” you have to
sudo edit /etc/hosts
and change it there, too!