how do you currently do service discovery w/ Docker and CoreOS without MESOS or Kubernetes?
The whole thing is pluggable and can use various distributed state backends (etcd, zookeeper etc) or IP connectivity backends (veth, macvlan, vxlan, openvpn etc) without changing your application. Service discovery uses DNS so you don't need to modify your application to take advantage of it. It's probably the most significant change to Docker in the last year.
This will make the integration with Kubernetes smoother. Currently Google is forced to rip out Docker's native networking stack because it is not flexible enough for their opinionated networking model. This causes many Docker applications to break in Kubernetes today. That problem should go away with Docker 1.7+ because Google-style networking can be expressed as a Docker plugin, which Kubernetes can load programmatically as part of its orchestration. An added benefit is that you can augment Docker with Google-style networking even if you use Kubernetes competitors like Mesos, Swarm, Cloudfoundry etc.
(EDIT added details more relevant to Kubernetes)
Sorry about the barrage of questions. As you can probably guess, I'm very interested in trying this out.
On a past project I did service discovery with Docker and CoreOS using SkyDNS with etcd. Services would register their network location in etcd and SkyDNS would translate those entries into DNS records. SkyDNS ran on every host and the app-level containers linked to the SkyDNS container.
If a container was moved across hosts, the etcd entry would be updated automatically and eventually the updated DNS entry for that service would propagate across the cluster.