The following is excerpted from How to trace your ancestors in Norway, by the Royal Norwegian Ministry of Foreign Affairs:

In the old days, Norwegians were identified by their Christian name and their father's name, plus the appropriate suffix. For example, Olav Håkonsen meant that this man was the son of Håkon. (The surname might also be spelled "Håkonsson" or "Håkonsøn.") And Sigrid Håkonsdatter was the daughter of Håkon. (The surname might also be spelled "Håkonsdotter").

In addition, a third name was often used. This was usually a farm name. This "surname" did not necessarily identify a family or a relationship; it signified a place of residence. If farmer Ole Olsen Li moved from Li to another farm, such as Dal, he would then be known as Ole Olsen Dal. A farm laborer could be named in the same way, even though he was not related to the farmer.

Sometimes, however, the preposition "på" (meaning "at") was placed between the patronymic and the farm name, indicating that the person in question was employed at that particular farm. Similarly, a tenant farmer (a cotter or husmann) was often listed in the official registers under the name of the farm to which his little home belonged. Sometimes the preposition "under" was put in front of the place-name. In this way, a cotter connected with the farm Lunde might be called Hans Petersen Lunde, or sometimes Lunde-eie (eie = possession), even if his home locally was called something else.

You should realize, therefore, that a surname in addition to the Christian name and the patronymic is not always the same as a modern family name. Family names in Norway are, in fact, a product of only the last few generations, except among the traditional upper classes (the clergy, military, civil servants, and the wealthy bourgeoisie). In Norway, the use of fixed family names was not made compulsory by law until 1925.

On arrival in the United States, Norwegian immigrants either already had three names or, in many cases, adopted a third one. Usually this third name was the name of the farm they had just come from. Sometimes the immigrants might take the name of another farm where they had once lived. Many Norwegians dropped the old farm names, however, and adopted patronymics as their surname. In the United States, Ole Andersen and his son Anders Olsen would in most cases take the same surname, either Anderson or Olson.

On the whole, the immigrants were not very particular about which surnames they adopted. The most important factor was apparently whether the name could be written and pronounced in English. In America, names such as Nelson and Johnson were already widely known and much easier to pronounce than most Norwegian farm names. Even if the original farm name was retained as a surname, it was often altered and modified so much under the influence of the new language that it is now unrecognizable.

Christian names were also sometimes changed. The first names and patronymics of immigrants were often spelled out phonetically by the immigration officer or the census taker in the United States. For example, Håkonsen might become Hawkinson. Or sometimes English equivalents might be given. For instance, Gulbrand might be changed to Gilbert, Guri to Julia, and so on.

Speaking of names, your search might benefit from a unique Norwegian custom. In Norway, especially in the rural districts, there have long been very strict rules about naming descendants. Some of these rules persist even today. It was customary, for example, for the eldest son to be named after his paternal grandfather and the second son after his maternal grandfather. In a similar fashion, the eldest and second daughters were named after the respective grandmothers.
After the grandparents' names had been used, the great-grandparents' names were the next to be given, although without strict rules as to the order. Special circumstances might interfere with these rules. For example, the name of a deceased spouse was to be used first; and the name of the father or mother was given if the child was baptized after a parent's death.
According to a Norwegian proverb: "The name and the farm must go together." This meant that a child who was intended to be the owner of the farm upon reaching maturity should be given the name of a previous owner, whether a relative or not.

Excerpt from the NATCHEZ TRACE NEWSLETTER:

(Why you cannot read some Census Records)
"I am a census taker for the city of baffalow. Our city has groan very fast in resent years and now in 1865, it has becum a hard and time consuming job to count all the peephil. There are not many that can do this work, as it is nesesarie to have an ejchuashun, which a lot of pursons still do not have. Anuther atribeart needed for this job is good spelling for many of the peephill to be counted can hardly speek inglish, let alone spel there names!"