Old Maps Online: A collaboration that brings together over 400,000 public domain maps online. A rich federated collection with a well maintained and intuitive map based search interface. Many of the other collections listed below are available here as well, so this is often a good place to start.
David Rumsey Map Collection: Over 98,000 historical maps from the 16th to the 20th centuries. Well documented collection with good quality, high-resolution images.
Library of Congress Map Collections: Over 38,000 of the LOC's map collection is scanned and available through their online collections. Worldwide coverage, although the United States is an obvious focus.
USGS Map Locator: Access to all scanned and georeferenced editions of USGS topographical maps, current and historical.
NOAA Office of Coast Survey Historical Map & Chart Collection: Historical navigation charts, scanned and georeferenced.
United States National Archives has thousands of maps available with an emphasis on US diplomatic and military history.
The British Library makes a number of collections available online.
ProQuest Sanborn Maps Geo Edition (UNI access):
Smithsonian Maps Catalog: The National Museum of Natural History has an online collection of over 30,000 maps.
United Nations Cartographic Section: A number of UN produced general and mission-related maps are available here.
University of Texas Perry-Castañeda Library Map Collection Online: The UT-Austin Map Library has scanned a large number of public domain maps at varying resolutions. Many of these are government produced maps and includes a number of AMS and CIA sheets.