[k-godwin]

1) Agreements with ISPs [most accurate]

2) IP Spidering via traceroutes / RIPE/etc data.

3) Agreements with third parties that have IP/Address mapping due to data supplied from users. [least accurate]

That'd be my guess anyway.

[NathanOsullivan]

They also have a form on their site to submit corrections. Maxmind's db is so prevalent now, I suspect (indirect) users submit all the info they need nowadays.