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.
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.