Esses serviços usam um banco de dados Geo-IP para fazer suas pesquisas de endereços IP em locais físicos. Alguns bancos de dados são baratos, alguns são (muito) caros - isso depende do nível de granularidade desejado.
Quanto a como realmente fazer isso, eu tenho medo de não poder derramar muita luz. Gostaria de extrair cada linha em um banco de dados e fazer pesquisas em uma tabela GeoIP - mas há maneiras possivelmente mais eficientes de fazer isso.