DNS Service Discovery is just a convention for finding services by first looking for a PTR record, eg:
$ dig +short ptr _http._tcp.dns-sd.org
;; Truncated, retrying in TCP mode.
<< snipped >>
Then an SRV record, eg:
$ dig +short srv \ *\ Multicast\ DNS._http._tcp.dns-sd.org
0 0 80 multicastdns.org.
And finally a TXT record for anything not encapsulated by the SRV record:
$ dig +short txt \ *\ Multicast\ DNS._http._tcp.dns-sd.org
The end result of the above would be an entry titled " * Multicast DNS" that would link to http://multicastdns.org:80/. You might ask how a DNS-SD aware client would know how to look up these records on dns-sd.org? Well it would either have to be explicitly told (configured manually) or it'd have to look at the systems search domains which could be configured via DHCP.
DHCP daemons can maintain records for the leases they give out by either being tightly coupled to a DNS daemon (eg: dnsmasq) or by sending update requests to a DNS server. Generally the later is done using TSIG'd DNS update requests but the method varies with DNS/DHCP servers used - this is pretty common with ISC BIND + DHCP and the Microsoft stack which uses a similar method.
Multicast DNS removes much of the hassle involved in setting up an environment like the above by making clients responsible for advertising their records. It's not without it's own quirks though - although it's got DNS in it's name, (unicast) DNS and mDNS don't interope, they exist in parallel which leads to clashes in environments that use the ".local" namespace (default for mDNS stacks) with their local unicast DNS. You can also end up with unexpected hostnames — if for example two clients vie for the same hostname, one will lose and retry with a number appended (this behaviour can be changed). That said, in a small environment this is not likely to become an issue.
mDNS setup is a matter of installing Bonjour on Windows or Avahi on UNIX like systems. OS X has Bonjour out of the box. Once installed, you should be able to access another machine via it's hostname with ".local" appended. Whilst it's possible to change from the default ".local" namespace it is a bit of a hassle.