How to reach a host in the same network by hostname?

Your /etc/nsswitch.conf should already have this for mDNS (avahi):

hosts:          files mdns4_minimal [NOTFOUND=return] dns mdns4

Just install avahi-daemon on the machines you want talking to eachother, and you should be set to use HOSTNAME.local like this:

ssh yourmachine.local

An alternative is to add an entry in your /etc/hosts file:

gksudo gedit /etc/hosts

An entry takes the form 123.123.123.123 host.domain or just 123.123.123.123 host.

If you do that, you can now for example ssh host and it will connect to 123.123.123.123