Seu /etc/nsswitch.conf já deve ter isso para o mDNS (avahi):
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
Basta instalar avahi-daemon
nas máquinas que você deseja conversar entre si, e você deve estar configurado para usar HOSTNAME.local assim:
ssh yourmachine.local