Short Answer:
I don't know. It probably varied a lot among different medieval societies.
Long Answer:
Part One.
I know that in Wales it was common to be able to recite one's patrilineal ancestry for a number of generations back. Therefore people should have been able to keep track of their agnatic (male lineage only) first, second, third, etc. cousins and so on.
That was certainly true for the royal, noble, and landowning classes in Wales. I note that in Wales the landowning class was an exceptionally large percentage of the population compared to most medieval European societies. I am not sure whether ordinary Welsh peasants would also have known their pedigrees for several generations back and known all of their closer cousins.
There is one line of evidence that suggests that as the Middle Ages passed it may have become more and more necessary for people to keep track of their ancestors and of all their cousins to several degrees of relationship, and that this may have become necessary even for free and unfree peasants.
As the power and influence of the Christian Church increased in Europe, and the power of what would become the Roman Catholic Church increased in Western and Central Europe, the Christian Clergy began to take more and more control of marriage.
For most of Western history, marriage was a private contract between two families. Until the 16th century, Christian churches accepted the validity of a marriage on the basis of a couple’s declarations. If two people claimed that they had exchanged marital vows—even without witnesses—the Catholic Church accepted that they were validly married[citation needed].
https://en.wikipedia.org/wiki/Marriage_license1
The Christian clergy began to demand that only persons of legitimate birth be allowed to inherit property, from the largest kingdoms down to the smallest patch of land. Naturally the Church's influence began to take effect with the most public and prominent inheritances first, and later began to control smaller and smaller inheritances.
My long answer to this question:
Why couldn't bastards inherit titles?2
Lists 24 examples from 810 to 1918 of persons of illegitimate birth inheriting thrones or of failed attempts to make illegitimate children heirs to thrones, or of monarchs or their heirs having problems with claims that they were of illegitimate birth.
Note that the first 12 of those 24 examples happened in the 480 years between 810 and 1290, and the next twelve happened in the 628 years between 1290 and 1918. There are only five examples listed in 520 years since 1500, and there is over 200 years between the last two examples. Clearly the possibility of persons of illegitimate birth becoming monarchs, or even trying to become monarchs, was getting lower and lower over time.
And see here:
Which bastards became kings?3
Naturally the clergy concentrated at first on limiting the heirs of kings and major nobles to legitimately born children, but they extended it down to lower and lower ranks over time until all Christian Europeans who wanted to leave property to their children had to have a Christian marriage or at least one which the Christian church would accept as a valid marriage.
The Christian clergy also began to regulate who could marry who. Most societies had customs or laws forbidding incest, marriage and/or sex between close relatives such as parents and children, brothers and sisters, and maybe a few more distant relatives.
But the Christian clergy, in their lust for social control, began to define which relationships constituted incest and which were permitted. So they began to forbid cousin marriages and gradually increased how distant a relationship counted as forbidden. Biological relationships are called consanguinity in the context of marriage.
Under Roman civil law, which early canon law of the Catholic Church followed, couples were forbidden to marry if they were within four degrees of consanguinity.4 In the ninth century the church raised the number of prohibited degrees to seven and changed the method by which they were calculated.4 This meant that the nobility struggled to find partners to marry, as the pool of non-related prospective spouses became smaller. They had to either defy the church's position or look elsewhere for eligible marriage candidates.4 In 1215 the Fourth Lateran Council made what they believed was a necessary change to canon law reducing the number of prohibited degrees of consanguinity from seven back to four.5 The method of calculating prohibited degrees was changed also: Instead of the former practice of counting up to the common ancestor then down to the proposed spouse, the new law computed consanguinity by counting back to the common ancestor.4 In the Roman Catholic Church, unknowingly marrying a closely consanguineous blood relative was grounds for a declaration of nullity, but during the eleventh and twelfth centuries dispensations were granted with increasing frequency due to the thousands of persons encompassed in the prohibition at seven degrees and the hardships this posed for finding potential spouses.6
After 1215, the general rule was that while fourth cousins could marry without dispensation, generally the need for dispensations was greatly reduced.6 In fourteenth century England, for example, papal dispensations for annulments due to consanguinity (and affinity) were relatively few.7
https://en.wikipedia.org/wiki/Consanguinity#Christianity8
Many monarchs and nobles had to pay to get dispensations to marry cousins within the prohibited degrees of consanguinity. And if it was discovered that a married couple was within the prohibited degrees the marriage could be annulled.
For example, Emperor Frederick I (1122-1190) had his first marriage to Adelheid of Vohburg (c. 1125-after 1187) annulled in 1153 on grounds of consanguinity. I have found several relationships between them, but the one that was used as the basis for annulling the marriage was apparently that they were either fourth or fifth cousins, once removed. I discuss their relationships below in Part Two for those interested.
Many nobles had to get dispensations for consanguinity in order to get married. And I suspect that some nobles deliberately omitted one of the forbidden relationships when applying for a dispensation, in order to have it in reserve to "discover" if they ever wanted or needed to apply for an annulment.
It was also possible for marriages to be prohibited or annulled for reasons of affinity.
In Catholic canon law, affinity is an impediment to marriage of a couple due to the relationship which either party has as a result of a kinship relationship created by another marriage or as a result of extramarital intercourse. The relationships that give rise to the impediment have varied over time. Marriages and sexual relations between people in an affinity relationship are regarded as incestuous.
Roman civil law prohibited marriages within four degrees of consanguinity5 but had no degrees of affinity with regards to marriage. However, the rule was that, if an issue of affinity arose, at whatever consanguineal level a couple was joined was considered the same level as regarded affinity.6 Roman civil laws prohibited any marriage between parents and children, either in the ascending or descending line ad infinitum.6 Adoption was considered the same as affinity in that an adoptive father could not marry an unemancipated daughter or granddaughter even if the adoption had been dissolved.6 Slaves, as such, could not contract a legal marriage, but if freed were then subject to the general rules.7 Also a marriage contracted within the prohibited degrees of consanguinity or affinity if contracted bona fide, out of ignorance of any impediments, is allowed to stand and any children of this union were considered legitimate.7
Regarding itself as not being bound by Old Testament commandments, the early Christian church followed Roman civil law, as the law of the land.8 The Christian emperors modified the rules from time to time and extended the civil law impediment to the first degree of collateral affinity. The church extended the impediment to relationships created by illicit intercourse. The Council of Elvira (c. 300), prohibited the marriage of a widower with his deceased wife's sister.9 The prohibition became slowly more extensive. By the early 9th century the Western Church had increased the number of prohibited degrees of consanguinity from four to seven.10 The method of calculating relationships was also changed to simply count the number of generations back to a common ancestor.10 The church also prohibited affinity to the same seven degrees.9 While the impediment of affinity is close to but not as compelling as that of consanguinity, the reasoning behind the prohibited degrees of affinity being treated the same as that of consanguinity is the nearness to the blood relatives by the very act of sexual intercourse.9
Prior to the Fourth Council of the Lateran (1215), the Church recognized two additional forms of affinity.9 Firstly, when a man married a widow, her relatives as well as those of her former husband were considered the man's relatives and treated as if they were his blood relatives.9 Secondly, if the woman's first husband had been a widower then the blood relatives of his first wife became the woman's relatives and by her subsequent marriage, were also the new husband's relatives by affinity.9 Also, a woman's children by a deceased husband, as well as the children of her husband by a deceased wife, were considered related by affinity.9 So the subsequent marriages of step-siblings carried the same prohibitions as if they were related by blood. The principle established was "affinity begot affinity."8
The Fourth Lateran Council removed the second type of affinity rule and the new axiom became: "affinity does not beget affinity", which is the principle followed in the modern Catholic church.9 It also limited both affinity and consanguinity prohibitions to the fourth degree, but retained the same method of calculating, counting back to a common ancestor.11 The Council of Trent (1545-1563) limited the impediment to marriage on account of affinity in cases when the affinity is created out of marriage (e.g., by force or extra-matrimonial intercourse) to the second degree of affinity.
https://en.wikipedia.org/wiki/Affinity_(canon_law)12
So medieval nobles also had to watch out for persons considered to be related in the forbidden degree because some cousin of the would be husband had married some cousin of the would be wife.
The Middle Ages lasted from about 500 to 1500. I am not a expert on the social history of the Middle Ages. But If the church began to regulate the marriages of free and unfree peasants as much as it regulated the marriages of monarchs and nobles, the peasants would have had to have had considerable genealogical knowledge of their first, second, & third, cousins.
If no peasants knew their relatives beyond their first cousins, nobody would be able to object to the marriage of two peasants on the grounds that they were second cousins or third cousins or something and thus had to get a dispensation before marrying.
I note that Banns of Marriage were instituted in the Middle Ages.
The banns of marriage, commonly known simply as the "banns" or "bans" /bænz/ (from a Middle English word meaning "proclamation", rooted in Frankish and from there to Old French2), are the public announcement in a Christian parish church or in the town council of an impending marriage between two specified persons. It is commonly associated with the Catholic Church, the Church of England, and the Church of Sweden, and with other denominations whose traditions are similar; in 1983, the Roman Catholic Church removed the requirement for banns and left it to individual national bishops' conferences to decide whether to continue this practice, but in most Catholic countries the banns are still published.
The purpose of banns is to enable anyone to raise any canonical or civil legal impediment to the marriage, so as to prevent marriages that are invalid. Impediments vary between legal jurisdictions, but would normally include a pre-existing marriage that has been neither dissolved nor annulled, a vow of celibacy, lack of consent, or the couple's being related within the prohibited degrees of kinship.
https://en.wikipedia.org/wiki/Banns_of_marriage13
The original Catholic Canon law on the subject, intended to prevent clandestine marriages, was decreed in Canon 51 of the Lateran IV Council in 1215; until then, the public announcement in church of marriages to be contracted was only made in some areas.3 The Council of Trent on 11 November 1563 (Sess. XXIV, De ref. matr., c. i) made the provisions more precise: before the celebration of any marriage, the names of the contracting parties should be announced publicly in the church during Mass, by the parish priests of both parties on three consecutive Holy Days.4 Although the requirement was straightforward in canon law, complications sometimes arose in a marriage between a Catholic and a non-Catholic, when one of the parties to the marriage did not have a home parish in the Roman Catholic Church.[citation needed]
Marriage licenses were introduced in the 14th century, to allow the usual notice period under banns to be waived, on payment of a fee and accompanied by a sworn declaration that there was no canonical impediment to the marriage.
https://en.wikipedia.org/wiki/Banns_of_marriage#Roman_Catholic_Church
Since consanguinity was one of the possible impediments to marriage, and since the use of Banns of marriage implied a degree of hope that any impediments to marriage will be known to some of the people who hear the Banns, it is possible that the Banns of marriage implied some knowledge of their genealogy and their neighbors' genealogy among some of the peasants and country people.
Thus I suspect that in an unknown percentage of the cases, some of the peasants would know which people in their village were related to them within the forbidden degrees.
Part Two.
The relationship that was the basis of the annulment of the marriage of Frederick I Barbarossa and his first wife Adelheid of vohburg.
Adelheid's mother was probably Adelheid of Poland, daughter of Wladyslaw I Herman. Adelheid of Poland's full sister Agnes's ancestry to great great grandparents is given here:
https://en.wikipedia.org/wiki/Agnes_I,_Abbess_of_Quedlinburg4
And Frederick's ancestry to great grandparents is given here:
https://en.wikipedia.org/wiki/Frederick_I,_Holy_Roman_Emperor#Ancestry9
Frederick was a great great grandson of Emperor Henry III while Adelheid of Vohburg was a great granddaughter of Emperor Henry III, making them third cousins once removed.
I note that Frederick I was also a great great great great grandson (through the mothers all the way) of Matilda, daughter of Emperor Otto II and Empress Theophanu, and Adelheid of Vohburg was a great great great granddaughter of Matilda, daughter of Emperor Otto II and Empress Theophanu, thus making them 5th cousins once removed.
But I have found a source claiming that another relationship was involved in the marriage annulment of Frederick I and Adelheid of Vohburg.
Emperor Frederick I (1122-1190) was the son of Duke Frederick II the One Eyed of Swabia (1090-1147), son of Duke Frederick I of Swabia (1050?-1105) [and his wife Princess Agnes (1072/73-1143) daughter of Emperor Henry IV]. Duke Frederick I of Swabia (1050?-1105) was the son of Frederick von Buren (d. 1068?), Count Palatine of Swabia, son of Frederick Count in Sundgau (d. after July 1027). The name of this Frederick's father is unknown, but it is easy to guess that it might have been Frederick.
https://fmg.ac/Projects/MedLands/SWABIA.htm#FriedrichIStaufenSwabiadied1105B10
https://fmg.ac/Projects/MedLands/WURTTEMBERG.htm#FriedrichIStaufenSwabiadied1105A14
A noble named Landolt or Lanzelin who died in 991 had four sons. One son, named Radbot, was the ancestor of the House of Habsburg. Another son, named Landolt or Lanzelin, Count of Altenburg (d. after 1027), was the ancestor of the House of Zahringen. The younger Landolt or Lanzelin married Bertha, sister of Fredrick Count in Sundgau, the great great grandfather of Emperor Frederick I, according to the papers relating to the annulment of the marriage of Emperor Frederick i to Adelheid of Vohburg.
Landolt/Lanzelin and Bertha had a son Bezzelin (d. 1024?) who had a son Berthold (d. 1078) who became Duke of Carinthia and Margrave of Verona. Duke Berthold's son Hermann (1045/48-1074) became the ancestor of the Margraves and Grand Dukes of Baden, and another son Berthold (1050?-1111) became the first Duke of Zahringen. Herman and Berthold's sister Liutgarde (d. 1119) married Diepold II von Giengen, Margrave in Nordgau.
https://fmg.ac/Projects/MedLands/BADEN.htm#_Toc5077636265
Their children included Diepold III, Margrave of Vohburg (d. 1146).
https://fmg.ac/Projects/MedLands/BAVARIAN%20NOBILITY.htm#DiepoldIIChamNordgaudied10786
Diepold III, Margrave of Vohburg (d. 1146), was the father of Adela or Adelheid of Vohburg, I note that this source makes her the daughter of Diepold III's second wife, Kunigunde of Beichlingen, instead of his first wife Adelheid of Poland, which may remove the relationships through Adelheid of Poland if correct. If Adelheid of Vohburg's mother was Kunigunde of Beichlingen that would still make her a great great great granddaughter of Mathilda, daughter of Emperor Otto II and Empress Theophanu and thus a cousin of Frederick I on that side.
https://fmg.ac/Projects/MedLands/BAVARIAN%20NOBILITY.htm#DiepoldIIIVohburgdied1146B7
So Emperor Fredrick I was the great great great grandson of the un named parents of Frederick Count in Sundgau and his sister Bertha, and Emperor Fredrick's first wife Adelheid of Vohburg was the great great great great granddaughter of the un named parents of Frederick Count in Sundgau and his sister Bertha, making them either fourth cousins once removed or fifth cousins once removed, I think.
