For example, a man named Jón Stefánsson has a son named Fjalar. Fjalar's last name will not be Stefánsson like his father's, it will become Fjalar Jónsson, mentioning literally that Fjalar is the son of Jón.
The same goes for females. Jón Stefánsson's daughter Kata would not have the last name Stefánsson, she would have the name Jónsdóttir. Again, the last name literally means "Jón's daughter".
The vast majority of Iceland carries the name of the father, but in some cases the mother's name is used, for various reasons. Sometimes either the child or legal parent wishes to end social ties with the father, some feminists use it as a statement, and yet others simply find it a matter of style and nothing more. In that case, the convention is entirely the same. Fjalar, the son of Bryndís, will have the full name of Fjalar Bryndísarson (literally meaning "the son of Bryndís").
Foreigners often find it strange that Icelanders formally address others by their first name. For example, current prime minister Davíð Oddsson would not be addressed as Oddsson by another Icelander, he would either be addressed only by his first name (or first and second if he had one), or his full name. The cultural meaning of an Icelander's last name is not that it's a part of one's name, but a short description of who one is. Davíð is Oddsson (a son of Oddur), it's only legally a part of his name. Culturally it is a definition of from whom he's begotten, even if that definition is seemingly vague.
Another good example of formally addressing someone, would be the Icelandic singer and actress Björk. Björk is commonly mistaken for an artist's name or an artist's expression, like the artist name "Sting". However, Björk is simply Björk Guðmundsdóttir's first name, as any Icelander would address her, whether formally or casually.