Well, seeing as "Norse" typically refers to late Iron Age and early Scandniavian-Medieval periods (700-1300 or so), then Norse people didn't really have patronymics or surnames. Names like "Leif Eriksson" for the supposed discoverer of America are modern-day projections of later naming customs back in time, for the sake of convenience as there are a lot of Leifs out there. These patronymics are not quite 'surnames' though; it is not customary to refer to people by them alone; Scandinavian historians would write "Leif" or "Leif Eriksson" but not refer to him as "Eriksson" alone. This remains the custom to present day in Iceland, where patronymics are still in use. (so e.g. saying "President Guðni" would be preferable over "President Jóhannesson")

Another example where names are projected back in time is the nobility, where in medieval Scandinavian contexts one might see things like "Karl Knutsson (Bonde)" (sometimes without parentheses), just to clarify he belonged to the house of Bonde even though they did not use it as a surname yet at that time.

But originally they did not use patronymics at all. People had a name, and perhaps also a byname, which could be "X's son" but also something else, like "Fat Erik". Scandinavians did not begin to use patronymics more systematically until the end of the Middle Ages. For example here's a list of medieval vicars of Skänninge - most medieval ones only have a first name. For instance the fellow named Sten is written as such as he was probably only ever referred to as such in documents. In formal contexts in his own day he would formally have been addressed as Herr Sten.

It's only from the early 1500s forward in this example that everyone has patronymics (although they're written here as they were in the texts of the era, in Latinized forms; Erici for Eriksson, Haquini for Håkansson, Caroli for Karlsson, Johannis for Johansson) the list continues like that until the 17th century when the clergy specifically began to invent their own latinized names (e.g. Nericius for someone from the province of Närke), which is also representative of the broader trend.

By this point the Danish word for "son" is søn by the late Middle Ages, so their patronymics ended with -søn. As Norway used Danish (more or less) as its written language standard until the late 19th century, Norwegian patronymics used _-søn as well, even though the word is originally son in Norwegian (and still is in the less Danish-influence dialects) . The spelling of which in names changed to -sen in the second half of the 18th century into the 19th century. In Sweden and Iceland, names end with -son. (So "Mikkelsson" specifically hasn't really existed, as it combines a Danish variant of Michael with a non-Danish suffix)

Traditionally, women would be named -dotter (Sweden), -datter (Denmark/Norway) and -dóttir (Iceland). They did not adopt their husband's name upon marriage if it was a patronymic. If it was a non-patronymic it'd be added to the end (e.g. if an Anna Andersdotter married Johan Holm, she'd become Anna Andersdotter Holm)

By the late 18th century, patronymics had begun to be seen as unmodern and parochial by many Scandianvians. Fixed surnames as people were using farther south became seen as a modern thing. People had begun to inherit patronyms rather than form new ones.

The liberal reformer Struensee in Denmark was first to legislate fixed surnames in the (then-) Danish duchies of Schleswig-Holstein in 1771. In 1828, Denmark passed a "baptismal law" mandating heritable names, although in certain regions patronymics continued for another half-century. Interestingly, -datter names went out of fashion somewhat earlier, and thus for a short while in the early 1800s, women in Denmark were being born with patronymics with -sen after their father's name.

In Sweden and Norway, the tradition continued longer, until the late 19th and early 20th century. (again with daughter-names disappearing first) The Norwegian name-law of 1928 mandated inheritance of names and thus banned patronymics. In Sweden, a similar law was passed by 1966, although very few were following the custom by that point.

These laws have themselves come to be considered unmodern since, and been abolished, with patronymics being allowed since 1982 in Sweden, 2002 in Norway and 2006 in Denmark. (although it has not lead to any significant revival of older naming customs)

As said, Iceland has retained the use of patronymics all along. The historic reason for this, is that as these customs were beginning to be perceived as old-fashioned in Scandinavia-proper in the late 18th and early 19th century, the national movement in Iceland (governed by Denmark at the time) was growing. The fact that their language was 'old-fashioned' and the Old Icelandic sagas was a centerpiece of that. They set about bringing back old words and getting rid of Danish words, and changing spellings, to make their language more similar to Old Icelandic and less similar to Danish. So if the Danes were perceiving patronymics as 'old-fashioned', then that was really all the more reason for Icelanders to keep using them - as being "more old-fashioned" than their Danish rulers was now an integral part of their emerging national identity.