I have a Linux server in my cupboard. My Windows machines can connect to it via its hostname. I have never configured any DNS server; all I did was assign the Linux box a name when I installed Ubuntu on it. It's running a Samba file server. 

My Macbook Pro doesn't recognize the host name. How can I make my Macbook find the machine the same way the Windows machines can? The Linux machine's IP is dynamically assigned via DHCP so I don't want to add a permanent entry to a hosts file or similar. (Despite this, the Windows machines can always find it.)