Los sistemas basados en Debian utilizan el archivo /etc/hostname para leer el hostname del sistema durante el inicio del mismo y se configura utilizando el script /etc/init.d/hostname.sh
Entramos a la consola y escribimos:
nano /etc/hostname

Cambiamos al nuevo hostname. Luego guardamos el archivo(Control + o) y cerramos (Control + x).

Por último, volvemos a escribir en la consola:
/etc/init.d/hostname.sh start


Ahora solo reiniciamos el sistema y ya aparecerá de forma permanentemente el nuevo hostname.
Fuente: Linux-OS