If the service does not exist in the local cluster (or it exists but has no healthy backend pods), the DNS query is automatically expanded to find the external IP address closest to the requestor's availability zone. KubeDNS performs this automatically and returns the corresponding CNAME. That will get further resolved to the IP address of one of the service's backing pods.

You don't have to rely on automatic DNS expansion. You can also provide the CNAME of a service in a particular cluster directly or in a particular region. For example, on GCE/GKE you can specify nginx.the-namespace.svc.europe-west1.example.com. That will get resolved to a backing pod of the service in one of the clusters in Europe (assuming there are clusters and healthy backing pods there).

External clients can't utilize DNS expansion, but if they want to target some restricted subset of the federation (such as a particular region) then they can provide the service's fully qualified CNAME just as the example. Since those names tend to be long and cumbersome, a good practice is to add some static convenience CNAME records:

eu.nginx.example.com        CNAME nginx.the-namespace.the-federation.svc.europe-west1.example.com.
us.nginx.example.com        CNAME nginx.the-namespace.the-federation.svc.us-central1.example.com.
nginx.example.com           CNAME nginx.the-namespace.the-federation.svc.example.com.  

The following diagram shows how a federated lookup works across multiple clusters: