Par défaut, Ubuntu inclut avahi. C'est une implémentation de zeroconf qui permet de résoudre les noms d'hôte des ordinateurs avec le nom virtuel ".local". Chaque fois que votre ordinateur essaie de se connecter à "hostname.local", avahi effectuera des diffusions sur le réseau local pour voir s'il y a des ordinateurs avec ce nom d'hôte. Les autres ordinateurs utilisant avahi (ou quelque chose de compatible) doivent répondre.
Si vous regardez dans /etc/nsswitch.conf, vous trouverez la ligne suivante:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
Le mdns4_minimal est le paramètre de configuration qui fait fonctionner cette redirection.
Votre question suggère en fait que avahi fonctionne correctement car vous dites que vous pouvez vous connecter à vos ordinateurs Ubuntu en utilisant "hostname.local". Cependant, vous ne le rendez pas clair ("Quand je leur ssh depuis un autre, ...") si vous essayez de vous connecter depuis un autre ordinateur Ubuntu ou depuis un autre ordinateur Windows. Sans installer d'autres logiciels tels que Bonjour, les ordinateurs Windows ne peuvent pas résoudre les noms "hostname.local" de type zeroconf.