Zeroconf means different things to different people. For example, the IETF Zeroconf working Group (perhaps "not-Working Group" would be more accurate, given the bickering going on) is only dealing with the IP address assignment problem. They are not specifying the name-to-address translation solution, nor are they dealing with service location.
The service location problem has a few answers (almost everyone has tried it, most implementations were pretty bad), but the IETF answer is Service Location Protocol v2 (see RFC2608, 2609, 2610, 2614 and some others - http://www.srvloc.org).
DNS SRV records (and TXT records, and PTR records, and NUL records - which makes up DNS Service Discovery - http://www.dns-sd.org) can help a bit, but suffer from not being able to do server side filtering. Imagine that you need to pull down the TXT records for every printer on a large network to find the one that can print on A2. SLPv2 can solve that problem.
There are also a couple of options for multicast DNS, one by Apple, and another by Microsoft. Both are pretty similar though.
For more info, including some implementation code, see http://zeroconf.sf.net