Someone types in your new server/domain, like "ijustmadethissite.com", or "newlocation.existingsite.com"

For their computer to resolve this domain name, it's going to call out to a DNS server, of which Google hosts a major one. It can be assumed that they log these names, and can then use that as a "notification" for a site coming up.