Por padrão, o Ubuntu inclui o avahi. Esta é uma implementação do zeroconf que permite que nomes de computadores sejam resolvidos com o nome ".local" virtual. Sempre que o seu computador tentar se conectar ao "hostname.local", o avahi executará transmissões de rede local para ver se há algum computador com esse nome de host. Outros computadores executando o avahi (ou algo compatível) devem responder.
Se você olhar em /etc/nsswitch.conf, você encontrará a seguinte linha:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
O mdns4_minimal é a configuração que faz esse redirecionamento funcionar.
Sua pergunta sugere que o avahi está sendo executado com sucesso, já que você diz que pode se conectar aos seus computadores Ubuntu usando o "hostname.local". No entanto, você não deixa claro ("Quando eu ssh para eles de outro, ...") se você está tentando se conectar de outro computador Ubuntu, ou de outro computador com Windows. Sem instalar outro software como o Bonjour, os computadores Windows não podem resolver os nomes "hostname.local" no estilo zeroconf.