My Ubuntu desktop at home seems to show up to windows boxes on the home lan and vice-versa, without me having to do anything to configure it.
Something I've done in the past in small office situations is set up a DNS server that knows the names of all the local machines and then proxies off to a real DNS server for anything else. Works really well actually and does not have to have a "real" domain to manage. YOu just have to make sure all the boxes on the LAN use it as a DNS server.