I would guess they are doing whois queries, but be careful that you don't inadvertently get yourself blocked.

Another point of caution-- perhaps it is just urban legend, but I've heard that some shady registrars capture the domain you're looking up temporarily so you can't register it anywhere else.

That (possibly unreasonable) fear is why I find myself checking the existence of a domain from the CLI before I actually use my registrar of choice to register it.