In Western Europe, there were several antroponymical fashions:
The "Central" fashion: Aymar de Sémur, Heinrich von Hohenstaufen, etc. There is a family coming from a certain castle or town, and the name gets stucked. It was common in France, Germany, Italy and Spain alike. Even though they took more important titles and duchies, their original name stood as the name of the family. The House of Lusignan became powerful, but it was still known as the House of Lusignan. The same for the Hohenstaufens, the Castillian House of Lara, the House of Châtillon... there are exceptions, of course.
The Spanish fashion was naming someone by his given name, then his father's name, then his family procedence. Thus we have "Pedro Fernández de Lara", whose father was Fernando López de Lara". Castillian tradition used the -ez as an evolution of Latin genitive -is, which sometimes indicates possession. The Catalan tradition was similar, but kept the names unaltered. "Ramon Borrell de Barcelona" was the son of Count Borrell, and his son was Berenguer Ramon, that is, "Berenguer son of Ramon". The tradition became weird when this Berenguer Ramon named his twin sons "Ramon Berenguer" and "Berenguer Ramon".
The Scandinavians didn't use to add any reference to the family, it was just the patronymic. Magnus Sverkersson, Halvdan Haraldsson, etc.
The Normans had a "latinized" version of that through the "Fitz-" patricle, meaning "son of". Thus, Robert of Chester, son of Eustace, was known as Robert FitzEustace. Henry II was known sometimes as Henry FitzEmpress (since his mother was Empress Maud).