This has come up before in other threads, questioning people’s claims to descent from Charlemagne and such.
It it both easy and hard. Luck is sometimes needed. To give an example, just two weeks ago I established my descent from old Norwegian kings on my father’s side. (I already explained how I got my descent from Charlemagne in an earlier thread.) What was involved:
Phase 1: A family history from the 1920’s gives the names of several ancestors born in Norway just before 1800. The history has since been confirmed by parish records.
Phase 2: The Norwegian national census for 1801 is online. Those ancestors are easily findable in the census. One of whom lived with her parents and an old grandparent, Thormod Biornsen, at Waage farm, Imsland, Rogaland, Norway. Again, parish records add confirmation.
Phase 4: (Skipping a few generations.) Most GedComs out there, and in particular much of the stuff at the LDS familysearch.com site, are crap. But one GedCom available at rootsweb “austring” is quite well done, complete with citations and supporting information. It gives the genealogy of some of the most prominent families of Rogaland. One key person is descended from an illegitimate daughter of King Haakon IV. (Whose saga based lineage goes back over another thousand years, but that’s a different type of genealogy.)
Phase 5: Exactly two generations span the gap from Thormod Biornsen to the austring file. I searched a lot of sources, but was careful to confim it all using the censuses in Rogaland from the 1660’s and 1701.
As the austring file points out, most people with origins from Rogaland can claim descent from royalty in this way. But on the other hand, there is a one person bottleneck. Remove that person from the genealogical histories and I couldn’t do it.
I am also lucky that this is Norway. Parish records typically go back to the 1700’s, which is far enough that you’ll usually find at least one prominent ancestor whose royal lineage might be known. Norway has been relatively untouched by war. Germany is practically a black hole because of wars. I don’t know about Scotland.