What does ".local" do?

Solution 1:

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.

Solution 2:

To fix your issue, you just need Avahi. This announces your Ubuntu machine names to the Windows lot.

sudo apt-get install avahi-daemon

machinename.local works thanks to another implementation of zeroconf (of which Avahi is also) called Bonjour, created (IIRC) by Apple. It's installed by default. I don't know why Avahi isn't also but given the confusion it causes people, it probably aught to be.

There's more on this on Wikipedia: http://en.wikipedia.org/wiki/.local