By default, Ubuntu includes avahi. This is an implementation of zeroconf which allows computer hostnames to be resolved with the virtual ".local" name. Whenever your computer tries to connect to "hostname.local", avahi will perform local network broadcasts to see if there any computers with that hostname. Other computers running avahi (or something compatible) should answer.
If you look in /etc/nsswitch.conf, you will find the following line:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
The mdns4_minimal is the configuration setting that makes this redirection work.
Your question actually suggests that avahi is running successfully as you say that you can connect to your Ubuntu computers using "hostname.local". However, you do not make it clear ("When I ssh to them from another, ...") if you are trying to connect from another Ubuntu computer, or from another Windows computer. Without installing other software such as Bonjour, Windows computers cannot resolve zeroconf-style "hostname.local" names.
nameserver
andsearch
)? How doesdig machine1
differ fromdig machine1.local
?