In short, they don’t have to know either.
There are many ways to do it, possibly the easiest way, and probably the most widely used, is to subscribe to a service like the “Newly Registered Whois Database” list on whoisdatacenter, which is why you get a million calls from people wanting to create a website for you after registering a domain without whois protection. It’s not free, they charge $20/month, another was $95, although there are ways to get the information for free, as it is public information, people are willing to pay for someone else to do the legwork.
From there, to get the DNS records of the domains, it’s easy, really, and can be scripted. Download list of new domains > query dns records for each site with something like nslookup (now you have a list of all the DNS entries for all the newly registered domains) > run nmap on said ips on the domains, do attacks, scan for vulnerabilities, exploits, whatever you want. Afterall, a site in the process of being setup is most likely to not yet be hardened, and may have a vulnerability that can be exploited. That’s why I don’t put the IP of my VPS or whatever on my DNS until they’re sufficiently hardened.
Whoisdatacenter just does that, but with the whois records, and checks when they were registered.
I found a script on sans.edu that tracks newly registered domain names, if you’re curious. It’s way too easy. The script, if you’re familiar with bash scripting, is quite easy to follow, too, so it’s worth a look if you’re interested. It’s very short.
I can totally understand not finding any of that, as the keywords aren’t what you would think unless you know how they’re finding the dns entries. You need the domain first, then you get the dns entries for that domain, which you can do with nslookup. The first part is a little harder, but with that script, or a subscription, that’s done easily, too. The keywords I used were “new registered domain names list”.
Hope that was helpful/informative.