There's a variety of different types of Internet
maps done local maps, global maps, and overlay maps.
There are a plethora of maps of small sections of the Internet. This can be an ISP or campus. These focus on a particular network, such as vBNS or Abilene. Generally, the connectivity is determined via the knowledge of the engineers or the design documents. The connectivity is described at a physical level.
Global maps try to display the connectivity of the entire Internet. This type of data is gathered via traceroute like technology. Thus, the maps generated look at the IP connectivity, which may differ from the physical connectivity due to technologies such as ATM and SONET. The gatherers of the data pick a collection of targets to traceroute to and union the results of those traces (sometimes with multiple starting locations). Since it isn't reasonable to try to trace to every IP address and remain a reasonable Internet citizen, the selection of the target addresses specifies the scope and depth of the map. Some choose specific targets, such as web servers or DNS servers, while other target networks.
Overlay maps visualize networks built upon on within the Internet. This includes measurement of the multicast networks, the connectivity of autonomous system, and the Gnutella network. The data collection for these networks is very specialized, as they generally work within the framework of the network they are visualizing.
Of course, collected the data is only one step in the process. You also have to layout the graph as well as determine who you're going to color it.
For a nice collection of graphical visualizations of network topologies (and other cybergeographies), go to http://www.cybergeography.org