The easiest method for finding "gateway" ancestors (those early American immigrants with noble and/or royal descent) is to consult published compendiums listing the various immigrants with their lineage.Four of the more common works are Frederick Lewis Weis' _Ancestral roots of seventeenth-century colonists_, 7th ed., Gary Boyd Roberts' _Royal descents of 500 immigrants_, David Faris' _Plantagenet Ancestry_, 2nd ed., and Weis' _Magna Charta sureties_.
Since Warren is a common surname, identifiers such as his birth and/or death dates (even approximate) along with the name of his spouse would help to narrow the search down.I found a William Warren (descendant of David I, king of Scotland), son of John, who married Catherine Gookin of Newport News, VA. in Roberts' work [p. 376], but nothing remotely matching your man in the other three compendiums.However, it looks as though this William that I found was a resident of VA, not MD.
Absence of a proposed lineage in the published works is not an indicator that a given ancestry is false; it just makes proving same more of a challenge.Royal lineages carry one's research back to the beginnings of recorded history, so it's only natural that many colonial immigrants have had their ancestries scrutinized for noble connections.
I did a Rootsweb search in their online pedigrees for a William Warren, place of death Maryland, and I came up with 17 different entries.Of course, these are submitter records and need to be proved, but they could be a start.You could also do an advanced google search and see if someone has an online pedigree that might be sourced [this find would be a rarity, but good online genealogies do exist].Reputable genealogists always provide sources for their data, so that interested searchers can check things out for themselves.
The biggest hurdle in proving any line of royal descent is getting from here to there, in other words, making a connection between the immigrant's adopted country and his place of origin in Europe.This is usually done by finding deeds, charters, wills (either in colonial records or in the place of origin) and/or inquisitions post mortem, to name a few of the more common types of records one might find for a given ancestor. Once this has been successfully accomplished, and you find that your ancestor links to the baronial class, then The Complete Peerage [a vetted authority on the British nobility] may well take you back to the beginnings.
Many early American colonial immigrants hailed from England.There are a number of places one can look for records of these people; often, early colonial wills have been abstracted or sometimes published in their entirety.English wills, particularly for the upper class, were mainly proved at the Canterbury Court [PCC] and are now fully indexed and downloadable online.Deeds and miscellanous records are increasingly finding their way to online indices from the various archival units in the UK.It takes a bit of practice with the various search engines, but the scope and coverage of Britain's electronic indices is staggering.
There is one further place to check; one often finds mention of unpublished lineages being discussed by professional genealogists and historians in online newsgroups and listservs.Here's such a board, with a searchable archives: