Support has been available for mDNS and related discovery services on most Linux distros for sometime. Static IPs or fixed hostnames are not scalable for cloud/rapid deployment/Vagrant. Ideally, there is some good hackery in the cloud init tools and also possibly generating a unique hostname based on a string template on first boot (along with reseal scripts).
Anyhow, here's the easy way to get mDNS working for most major OSes.
su - -c 'yum install -y avahi avahi-tools nss-mdns ;
service avahi-daemon start'
On Debian/Ubuntu: http://wiki.debian.org/ZeroConf
sudo su - -c 'apt-get install -y avahi-daemon avahi-discover nss-mdns ;
sudo invoke-rc.d avahi-daemon start'
On Arch: https://wiki.archlinux.org/index.php/Avahi
echo 'You won't need hand-holding here I assume.'
What's nice is this gets mDNS working on the Linux box the other way too, so you can usually just start pinging/ssh/etc to your Mac right way. Woot.
avahi-browse --all is very neat.
Don't forget the inbound firewall rule on the box acting as a server.
-A INPUT -d 126.96.36.199/32 -p udp -m udp --dport 5353 -m comment --comment "mDNS" -j ACCEPT
Also, configure with /etc/avahi/ and restart the daemon.
Incidentially, I am building a CentOS 6.2 x86_64 minimal appliance for a client on my MacBook Pro under VMware Fusion 4.x.
Perhaps someone will add the bit for making sure that the announcement work and publishing of services (esp. ssh and web urls) works correctly for Mac, Linux and even Windows clients.