Interoperability shouldn’t be an issue – that’s what a standardized protocol is <i>for</i>.  MacOS X has Bonjour already built-in.  On Linux you can simply require Avahi.  For Windows there seems to be a large selection of available ZeroConf libraries, depending on your implementation language (unless you want to simply require Apple’s “Bonjour Print Services for Windows” bundle).