Many historical maps of Maine are available online. The following sites have online collections:
The University of Maine in Orono, the Maine Historical Society, and Bowdoin College in Brunswick have large collections of maps and atlases. The Bangor Public Library is also a good source of maps.
The Family History Library has a few individual maps of Maine. These often show the locations of towns, rivers, roads, townships, and county boundaries. A few of the Maine maps in the Family History Library's collection are:
Carleton, Osgood. A Map of the District of Maine. N.p., N.d. Reprint. Originally published 1793. (FHL map case 974.1 E7c). This also includes a map containing the location of areas with the most Indian problems.
Greenleaf, Moses. Map Exhibiting the Principal Original Grants and Sales of Lands in the State of Maine. Ellsworth, Maine: Ellsworth American, 1977. (FHL map case 974.1 E7g).
Maine County Subdivisions, Towns, Plantations, Unorganized Territories, and Places. Washington, D.C.: U.S. Government Printing Office, 1977. (FHL map case 974.1 E7mc).
For individual locality map information, see the Place Search of the Family History Library Catalog under MAINE, [COUNTY], [TOWN] - MAPS.
Printable maps are also available from the National Atlas of the United States -- http://nationalatlas.gov/printable.html