A Norwegian has at least two names, a given name which comes first and a family name which comes last. In addition he can have other first names or family names - these are generally called middle names. Norwegian name laws are quite strict, both when it comes to naming a child and when changing your own name. Despite this, the flora of names can be quite dazzling. Many Norwegians have a name which is unique - nobody else in the world has a name exactly like theirs. Of course, this also has something to do with their country's sparse population.
By law, children are not to be given names that can be denigrating to them. This prevents a poor sprog from being named Sperm or Eejut by unhappy parents in search of revenge. Family names cannot become first names unless they have traditionally been known as such, and vice versa, first names can't be used as family names (so no Humbert Humbert in this country). There are also rules for spelling - fancy spellings with a foreign look are not encouraged. The law also prevents foreigners from giving unfortunate names to their child - the Turkish name Musa is a good example. In Norwegian, it means the mouse and is also slang for pussy. Jesus is not allowed, no matter how holy - to compensate, Judas and Lucifer are also forbidden.
Last names are also regulated. To adopt one, the person in question should have a strong connection to it - living in a place by that name or have a close relative known by it (mother's maiden name and spouse's name are acceptable). Certain rare family names, today the ones with less than 500 bearers, are protected. If you want to take the name without obtaining it through birth, adoption or marriage, all of them have to give you permission to take it.
The law of names, originally meant to protect the traditions of the country, has recently become much less strict than it used to be. Compared to the Icelandic naming system it is a liberal Utopia. Maybe they realised that the best traditions are the ones we make ourselves.
Norwegian names have a lot in common with other Scandinavian names, but some features are their own. Patronymics are similar to Danish ones in that they end in -sen, they are different from Swedish (and Icelandic) which end in -son. Also the given names have their own flavour, but this is hard to define without examples. So let's bring'em on!
Given names
I have earlier compared names to flowers, but they can also be like water, spreading over the country in waves. Norway has received impulses from different cultures at different times. One of the impulses has been names, and in them the results of these 'waves' can still be distinguished today.
Old Norse Names
The oldest names that are still in use today are from the Viking era. Some of them have much older roots, but the pre-old-Norse names look and sound extremely foreign now. The names of the vikings were supposed to give strength and protection. Traditionally they were made by combining a pre- and a suffix. The first part was often a god's name (Tor), a strong animal (Bjørn), or an object such as a stone or a weapon (Stein or Odd), while the latter part showed the gender of the bearer and had a comfortable meaning, such as fence/protection, gift, or warrior. Female suffixes are -gunn, -veig, -borg and -gerd, among others, while male ones can be -geir, -gard, -mund and -mod. Confused? You're not the only one. After a time, the vikings themselves didn't follow the rules precisely. Compound names were often shortened and new, short names were created. After Norway became Christian, priests tried to discourage the use of heathen names in favour of saintly ones, but did not fully succeed. Many names survived, and in modern times when interest in the saga time grew, these names and those of the old gods were revived.
Female names from this era: Aud, Bergljot, Frøydis, Gerd, Inga, Ingeborg, Gudrun, Ragnhild, Sigrid, Siv, Torborg, Åse.
Male names from this era: Arnfinn, Bjørn, Erlend, Hermod, Kjell, Kolbjørn, Oddgeir, Olav, Sverre, Tore, Torstein, Åmund
Christian Names
The names of apostles and saints were imported and generously applied as Norwegians got to know their new religion, after about 1000 AD. The names were translated and transformed to suit local needs, and many of them are hardly recognisable after their journey from Hebrew through Greek and Latin to Norwegian. Names to describe the new status of the bearer, such as Helga (holy) or Kristian (Christian) also arose now.
Female names from this era: Anna, Helga, Johanna, Kristina, Maria, Marit, Marta, Signe, Synnøve.
Male names from this era: Andreas, Helge, Jakob, Johannes, Jon, Kristian, Martin, Mikkel, Peter, Pål
Names from the south
Several factors spread names from further south in Europe to the north. Norway was under Danish rule for several centuries, which led to a steady import of names from that country. Although the names were not always unheard of earlier, the spelling was often different. Close trade relations with Hanseatic Germany in the west of the country let German names in along with the goods. Family names were also imported as people from these countries settled in Norway.
Female names from this era: Abelone, Dorte, Else, Karen, Margrete, Oline, Rikke
Male names from this era: Fredrik, Gustav, Henrik, Hermann, Jens, Jørgen, Kurt, Lars, Ludvig, Ole
Romantic influences from France and Italy gave rise to a lot of foreign-sounding names imported because of their beauty, primarily given to girls. The Sun King's splendour was the main reason for this.
Female names from this era: Annette, Beate, Camilla, Charlotte, Emilia, Louise
Male names from this era: Charles, Emil, Karl
Names from the west
Closer ties with England as well as cultural influences from across the pond led to an influx of many names from those countries. The names were most often imported in their shortened form, since those nicknames were most often heard in the cinema or on television. Some of these names became a normal part of Norwegian culture, while others, although perfectly normal in their country of origin, symbolise uneducated parents who get their influences from the telly, and foretell a bad future for the child.
Female names from this era: Betty, Edith, Harriet, Jane, Kitty, Lilly, Mary, May
Male names from this era: Arthur, Ben, Georg, Glenn, Henry, Harry, Jimmy, Ronny, Tim, Willy
Today's flowerbed of names is a rich mix of every influence. There is a tendency in Norway to leave the boring, traditional names and go for ones that are easy to spell and pronounce internationally. Names with the special Norwegian letter æ, ø and å are also slowly going out of fashion. It would be sad to see these original Norwegian names go, but it's highly unlikely that they'll disappear completely. They are nice, and while they are not exotically alluring today, they may be so in seventy years.
Family names
A person's last name is generally either an inherited patronymic or a place name, often the name of a farm. Personal characteristics (such as English Black) and crafts (i. e. Smith or Thatcher) are less common, but do exist.
It is possible to make a new family name, but very difficult. It's also possible to make a new patro- or matronymic from your father or mother's first name and -sen (son) or -datter (daughter) added to it. These can under the current law only become middle names and are not inheritable, however.
Last names used to be very fluid. They were not inherited, but used about a person according to his situation, to distinguish him from others. Therefore a person would be known by his patronymic or where he kept his home, whichever was convenient. With the breakup of traditional society this gradually changed, and by the 20th century most Norwegians had a name that followed the family. It was only in 1979 that this was definitely required by law, however, and some people did without even until then.
The most common surnames today are Hansen, Olsen and Johansen. Other very common names describing natural features are Haug and Ås (both mean Hill), Berg (Mountain) and Nes/Ness/Næss (Spit, but not in the salivating sense). Longer names are less frequent, but still exist in many variations. Random examples are Blakstad, Eidsvåg, Nyborg and Sandnes.
Disclaimer: A lot of the name examples are things I remember from name encyclopedias I have studied. I think I'm right, but may well be wrong. Also, of course, there are a lot of names omitted.
PS: Don't trust the Scandinavian names naming guide blindly if you want to create a believable Scandinavian character. Most of the surnames are Swedish and many of the given names are unfamiliar. A Norwegian named Elvis Johansson would be exteremely unlikely.