I understand the mathematics behind the statement, but don't understand how it's practical for descendants of Charlemagne to be everywhere in Europe and in all classes of society when social mobility and the ability to leave your local area were so proscribed throughout history. If my family has been consistently living in what is now Poland or Spain or Italy for millennia, how could we and all our neighbours have ancestors that breeder with the descendant of a Frankish noble? Did people travel around and change cultures more than I thought in the medieval period?
I think the sticking point here is that you're imagining all of our 'potential' ancestors as real and distinct people, whereas in reality we share a huge amount of them. If we start going backwards through our 2 parents, then 4 grandparents, then 8 great-grandparents etc, we eventually arrive at a number which in fact exceeds the number of people who have ever lived on the planet. It therefore follows that we are related to each other via these shared ancestors, rather than each being the progeny of distinct family trees.
A single person descended from this European, web-like lineage would only have to marry into one generation of your family in Poland or Spain or Italy to ensure that every single future descendant of theirs was now also related to Charlemagne. In this way, a European alive today is essentially related to the majority of Europeans alive between 600 and 1000 years ago.
The most recent common ancestor of every European today (except for recent immigrants to the Continent) was someone who lived in Europe in the surprisingly recent past—only about 600 years ago. In other words, all Europeans alive today have among their ancestors the same man or woman who lived around 1400...20 percent of the adult Europeans alive in 1000 would turn out to be the ancestors of no one living today (that is, they had no children or all their descendants eventually died childless); each of the remaining 80 percent would turn out to be a direct ancestor of every European living today.