Originally, like many other European peoples, Danes used only personal names and patronymics. Thus, Peter son of Rasmus would usually bear the name "Peter Rasmussen", the "-sen" particle being a drifted version of søn ("son"). A daughter would use "-datter" instead.
The first people in Denmark to acquire actual family names were, unsurprisingly, the nobility. In 1526, King Frederik I decreed that, henceforth, all noble families were to bear a family name. Many of these families already had de facto family names, based on the symbols on their coats of arms(e.g. Gyldenstjerne, Marsvin, Oxe, Munk, etc.), which had been in use for some time.
Over the 16th and 17th centuries, the custom of using specific family names spread into the ranks of the bourgeoisie and clergy, the latter often adopting latinised names (e.g. Pontoppidan, from Broby, "Bridge-town").
Among the peasantry, however, the use of personal names and patronymics remained entrenched, up into the early 19th century. Occasionally, people would add a village's name, or the name of a large farm, to their patonymic, but these had more of the character of cognomens than of actual family names. As a result, many people in a village would often have precisely the same name, complicating things for purposes of taxation and census-taking (which might possibly serve as an explanation).
The government of Denmark (at the time, an absolutist monarchy) tried to make reliable census-taking easier by introducing an order, dated May 30, 1828, which introduced fixed family names, "freezing" the existing patronymics. However, the wording was so unclear that it required a revision the following year. Henceforth, patronymics were to be official family names, and both sons and daughters should bear the "-sen" form of the name. This caused no little upset among the peasantry, who found the idea of calling daughters "son of" somebody ridiculous.
As a result, the peasantry by and large ignored the order, causing the government (of the now-constitutional monarchy) to issue a circular dated August 6, 1856, which made it clear that patonymics were now officially frozen once and for all. Even so, many peasant families opposed the new practice, and the old style names continued into the 1870s.
The result of the name laws was to create a huge population of Danes bearing patronymic-style surnames: Hansen, Jensen, Petersen, Rasmussen, etc. The only way to get a new surname was to apply for a royal patent. By the end of the 19th century, however, proposals were put forth in the Danish parliament to modify the legislation, and these were signed into law on April 22, 1904.
The new laws allowed people to adopt family names based on the cognomen of their parents or grandparents, or on the place names of property or lands owned by the family for at least two generations. A list of typical Danish placenames permitted for use as surnames was also compiled, and finally divorced women could apply to regain the use of their maiden names. To protect existing family names of prestigious families from being overrun by social climbers, a list of "protected" names was also compiled, and families could apply to have their name protected.
In recent years, legislation on names in Denmark has focussed mainly on personal names (particularly in the wake of the 1960s and 1970s, when many new and unusual names were introduced. A list of approved male and female first names is kept, and to have one's child named something not on the list requires an application. The list is regularly revised - but, of course, people who can prove a family or cultutral tradition for a particular name, will always be allowed to use it.
Another recent feature of Danish naming conventions is that the influx of new names has been hard to resist. In one notable case, a mother was determined to have her newborn son baptised "Christophpher" (a variant of the common names "Christopher" and "Kristoffer" not permitted under the laws, especially since it is also ridiculous, and violates the principle that names may not be deleterious to the child). With the unwavering determination of the very stupid, she persisted in defying the government, and finally won permission. Her son, now several years old, became legally "Christophpher", poor kid.
An older case is the case of the first Danish child born in an aeroplane, not long after the war. Her parents desperately wanted to commemorate the event by naming her "Flyvia Propella Madsen" (="Flightia Propella Madsen"). The ministry said no, and that was that. It was the "Propella" that did it...
"Flyvia", however, had already been used as a girl's name - in 1928. During a hard winter, Laura Knudsen, a woman living on the island of Saltholm, was about to give birth. Since the winter weather made it impossible to transport her to a hospital, a military plane transported a midwife to the island. In gratitude, the Knudsens named their daughter Stella Flyvia. This was approved.
Names, both personal names, family names and place names, are the subject of a whole branch of study at Danish universities. At Copenhagen University, there is the Department of Name Research, which advises the government (specifically, Kirkeministeriet, the Ministry of Ecclesiastical Affairs, which is in charge of administering the name laws) on the subject.
There are signs to indicate that the practice of "fantasy" names may be on the rise in Denmark. In the course of ten years (1992 to 2002, the number of cases where new (which is to say, previously unlisted) names had to be referred to the Ministry of Ecclesiastical Affairs for evaluation increased from 350 to 1050, an increase of exactly 200%.
In October, 2003, this sparked a debate in the media about the superstitious practice of numerology, which was blamed for part of the increase (the numerologists often recommending a name change as a remedy for all sorts of ills). Part of the reason for the debate may be the public attention granted to the practice by a television documentary about it, during the preceding summer.
Among the remedies debated for the "frivolous" name changes, which were blamed for wasting enormous ministry resources, were the introduction of fees for changing personal names. Hitherto, surname changes, which could potentially involve considerable and time-consuming research, had cost a fee of 3000 kroner - personal name changes had been free.
At the latest revision of this writeup, the debate remains open, and the fee system unchanged.