How do I find pre-1870 if I know old city names?

Where do I go to search pre-1870 church or farm records (or any other records) for Norway, especially if I do not know where the cities are for which I have names (eg, Hallingdal/Hollindol where property was swindled from Thorer Arneson Stavn; "Aasbeiter", which sounds like a city (one of Thorer's sons (Arni) worked there when very young); "Bondetjeneste", which sounds like a new city where Arni "had a chance to drive horses and chores them and do worthwhile work as a grown man"; "Lier by Drammen", where Arni worked till 1875 when he came to America at age 19; "Gire in Ness", where Arni's wife was from; Sahndalen/Sohndalen, where Arni's mother Barbro Trulsdatter Mjolid was from; "Nordre Sovre" where Barbro's grandfather was swindled out of the Gaard by his next oldest brother; and "a Brug called Bendik Plassen" where Knut moved after losing the Gaard)? Kara D. (Kosmatka) Ishii