Here are details of the machine I want to access using its hostname:

    $ hostname
    $ cat /etc/hosts	localhost	hostname

It's a default Debian 6 (Squeeze) install, so I didn't fiddle with anything yet.

This is what I get from a machine (running Debian Unstable) trying to access above machine:

    $ ping hostname
    ping: unknown host hostname
    $ ping
    ping: unknown host
    $ cat /etc/resolv.conf
    search company.local