Hosts on a local network can use mDNS to "self-publish" DNS names for other hosts to find them quickly and easily.  Windows XP can use [[http://www.apple.com/support/bonjour/|Apples "Bonjour"]] package, Macs come with the funcitionality built-in and many popular Linux distros use [[http://avahi.org/|Avahi]] to provide the functionality.

Sometimes on the Linux host the local firewall can get in the way of Avahi working correctly.

Here's the magic:

''iptables -A INPUT -p udp ----dst 224.0.0.251 ----dport 5353 -j ACCEPT''

You'll have to replace the tables with whatever you have on your local system, but the basic logic should flow.  

mDNS is a multicast protocol that runs on 224.0.0.251 port 5353, so your local mDNS client/server (in our case, Avahi) needs to be able to talk out to the multicast channel.