Michael Ramsey, in his excellent article on the meaning of “natural born citizen,” argues that the founders likely used that term with British precedent in mind. In a series of statutes, Parliament redefined the common-law definition of “natural born subject”—which meant born on UK territory, with some minor exceptions—to encompass people born on foreign territory to a British father, a necessary elaboration in an era when large numbers of British subjects spent years abroad roaming around in service of foreign-born British monarchs while spawning offspring. Blackstone discusses this history; the founders read Blackstone; ergo the founders likely had Blackstone in mind when they agreed on the term “natural born citizen,” replacing subject with citizen but preserving the meaning of “natural born.”
But did the population at large? Most people weren’t lawyers, fewer still read Blackstone, and in the current version of originalism—of which Cruz is an enthusiastic adherent—the relevant question is the “public meaning” of the Constitution when it was ratified. I checked Samuel Johnson’s dictionary, which does not contain an entry for “natural” but does include “nature.” The most pertinent of the definitions is “the regular course of things.” Citizenship, in the regular course of things, came to those who were born on U.S. territory. The complex process known as “naturalization”—by which an alien becomes a citizen after jumping through various hoops—reinforces this idea. People who are not citizens in the regular course of things (by birth on U.S. territory) can become citizens through operation of law.
The Constitution withholds the presidency from those who are “naturalized,” reserving the prize only for those whose citizenship is natural. The vast majority of Americans at the time who were not naturalized aliens were citizens of the various states because they were born in the states. Citizenship in “the regular course of things” would mean citizenship by virtue of birth on U.S. territory.
My argument would be strengthened if the practice in the states in the eighteenth century was to require people born abroad whose parents were U.S. (and/or state) citizens apply for naturalization. I am not aware of evidence in either direction.