У вашего /etc/nsswitch.conf уже есть это для mDNS (avahi):
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
Просто установите avahi-daemon на машины, с которыми вы хотите разговаривать друг с другом, и вы должны быть настроены на используйте HOSTNAME.local следующим образом:
ssh yourmachine.local