Civil and church records, as well as archival collections, are organized by geographic location. An important first step to locating these records is to determine your ancestors' town of origin. This can be further complicated by language and border changes, which means its important to consult resources like maps, gazetteers, atlases, guidebooks, and town directories.
Skorowidz Gazetteer Online to find parish locations
Spis Gazetteer, Volume 1, provinces and locations of civil registration offices
Mapa.Szukacz.pl with modern provinces, jurisdictions, population, postal codes
Historische Pläne und Grundrisse von Städten und Ortschaften in Polen , bibliography of old maps
The website of the Małopolskie Towarzystwo Genealogiczne [Little Poland Genealogical Society] - tons of digitized directories, address books, catalogs, schematisms, etc... helpful for the former province of Galicia.
Library of Congress research guide, Cartographic Resources for Genealogical Research: Eastern Europe and Russia