As I find better sources, I will try to come up with a comprehensive source for maps of Germany past and present. In the meantime, here is some information I took from http://www.schleisen.de :
Gazetteers and Maps
By far the most common situation is that one turns up a document which reveals the origin of the ancestor as a European town, either with no state listed, or listing a state that has changed its boundaries or no longer exists. Here are some tips about how to go about finding the place:
If you already know or are pretty sure that the place is inside modern Germany, your best bet is GEOserv. If GEOserv does not find it, you should consider consulting Der Grosse Shell - Atlas, a comprehensive road atlas of Germany (published annually by Mairs Geographischer Verlag) or RV Autoatlas from Genealogy Unlimited. If neither of these find it, consult Meyers Ortslexikon (Meyer's Gazetteer) published in 1912 which lists all towns in Germany or lost by Germany after either 20th-century world war. The Ortslexikon is available on microfiche from the Family History Centers.
On the other hand, if you think that the place is in Central Europe, try the JewishGen Shtetl Seeker, an interactive, fuzzy-search gazetteer with maps that includes 24 countries east of Germany, Austria and Slovenia (inclusive). If this doesn't work, you might try the Genealogisches Ortsverzeichnis (GOV) (Directory of Genealogical Locations) which is a project aiming at providing uniform access to a vast amount of genealogical data on geographical locations. For the time being, however, the emphasis is still at compiling the index of locations and their geographical positions: some 50,000 locations have been entered to date. This database (including coordinates and zip codes) may be downloaded. At the same time more volunteers entering data are still needed: the program to enter and submit data is also available online.
If you think the place is elsewhere in the world, try GEONet, the worldwide gazetteer.
If you follow all these steps and cannot find the place, post it to soc.genealogy.german to see if anyone else can help.
Once you do manage to ascertain which country the place is in today, you can view a map of the region at the Mapquest web site.
If it will help to look at maps depicting the historical borders, see our page on Historical maps (including on-line facilities and software packages).