Eles consultam do SERPRO https://www.loja.serpro.gov.br/consultacnpj, ou de alguma empresa como SERASA, Quod, ou similares...Se não me engano é possível conseguir esses dados com as juntas comerciais de cada município/estado, mas nesse caso, não sei como funciona.