Install Avahi, it like bonjour auto discovery but for linux, then tell it about your servers samba service.

$ sudo apt-get install avahi-daemon
$ cd /etc/avahi/services/
$ sudo wget https://raw.github.com/gist/1105096/0dc157711a85a08a1220ecb3fe94f069d2fcecec/etc_avahi_services_samba.service
$ sudo mv etc_avahi_services_samba.service samba.service
$ sudo restart avahi-daemon