Primeiro, verifique se você tem o daemon Avahi instalado. (Deve ser instalado por padrão no Ubuntu Desktop, mas não no servidor.)
sudo apt-get install avahi-daemon
Depois, para acessá-los, adicione ".local" ao final do nome, por exemplo
ssh machinename.local
Não tenho certeza se é possível remover a necessidade de adicionar .local