At time of answering, the question is: What's the most crucial issue when deciding Senator Cruz's citizenship?
The 14th Amendment to the US Constitution, Section 1, states:
All persons born or naturalized in the United States, and subject to the jurisdiction thereof, are citizens of the United States[.]
Cruz did not go through a naturalization process. He was also not born within the territorial limits of the US. If either of those facts were different, those would be the crucial issue.
Since they are not, we then look to the Naturalization Act of 1790, passed by the first Congress, which states that children born to citizen parents outside the United States are also citizens, specifically:
The children of citizens of the United States, that may be born beyond sea, or out of the limits of the United States, shall be considered as natural born citizens[.]
According to the Wikipedia article and/or sources it cites, this is the only legislation to use the phrase "natural born citizens" and it seems clear this is intended to refer to Article II, Section 1 of the Constitution which states a requirement:
No person except a natural born citizen, or a citizen of the United States, at the time of the adoption of this Constitution, shall be eligible to the office of President; neither shall any person be eligible to that office who shall not have attained to the age of thirty five years, and been fourteen Years a resident within the United States.
The 1790 Act was repealed and replaced in 1795, but the new law also contained the language (lacking "natural born"):
The children of citizens of the United States, born out of the limits and jurisdiction of the United States, shall be considered as citizens of the United States[.]
The specific laws have been further changed, as the naturalization process has, reintroducing ambiguity about the "natural born" requirement, but birthright citizenship from parents is not in question and the "natural born" aspect is not in this question.
So, to answer the question directly, the most crucial issue is: Were Cruz's parents citizens when Cruz was born?
Cruz's Wikipedia page says his father was not naturalized until later, but his mother was born in Wilmington, DE, which is in the United States, and so unless she renounced her citizenship she would have been a US citizen at the time of Cruz's birth. This means there's a crucial issue: Did Cruz's mother renounce her US citizenship before Cruz was born? "Kaithar" commented on this answer with speculation that she voted in a Canadian election at a time (1947-1977) when Canada didn't recognize dual citizenship in that it required its own citizens to give that up if they acquired foreign citizenship; "user102008" refutes that. However, if we don't want to end this issue-identifying answer at that question, let's assume the answer is "no" and that Cruz's mother was a US citizen when Cruz was born.
Then we have to see if birthright citizenship from parents extends to Cruz.
For this, we can look to Public Law 414 (66 Stat. 236), passed June 27, 1952, especially section 301(a)(7):
The following shall be nationals and citizens of the United States at birth:
A person born outside the geographical limits of the United States and its outlying possessions of parents one of whom is an alien, and the other a citizen of the United States who, prior to the birth of such person, was physically present in the United States or its outlying possessions for a period or periods totaling not less than ten years, at least five of which were after attaining the age of fourteen years: Provided, That any periods of honorable service in the Armed Forces of the United States by such citizen parent may be included in computing the physical presence requirements of this paragraph.
Side note: Section (4) (modern (d)) would matter if Cruz's father were considered a noncitizen national of the US, slightly relaxing the requirements so that the mother only had to spend only one continuous year in the US prior to the birth.
The armed forces exemption was broadened Nov. 6, 1966 to cover the parent (or their parent's) nonmilitary employment by the US government or certain international organizations. If that's relevant, this answer can be edited to expand on this point.
Section 309 of that law addresses children born out of wedlock, and says that section 301(a)(7) (quoted above) applies directly as if the parents were married, "if the paternity of such child is established while such child is under the age of twenty-one years by legitimation." To the best of my knowledge, section 301(a)(7) applies to Cruz. If I were wrong on that, we'd look to Section 309(c):
A person born, after December 23, 1952, outside the United States and out of wedlock shall be held to have acquired at birth the nationality status of his mother, if the mother had the nationality of the United States at the time of such person’s birth, and if the mother had previously been physically present in the United States or one of its outlying possessions for a continuous period of one year.
The equivalent of the first quote today is in 8 U.S. Code § 1401(g) if parents are married at the time of a child's birth, replacing "ten years, at least five" with "five years, at least two" (Nov. 14, 1986; see Section 12 in this law). The quote from 309(c) is now 8 U.S. Code § 1409(c).
So then the crucial question is: Did Cruz's mother spent the requisite period of time in the US before Cruz was born? Apparently she did, regardless of marital status, and if that's true it means Ted Cruz is a US citizen and has been since at least birth*. Again, the "natural born" aspect is omitted from this now-answered question.
The answer to the question you meant to ask (perhaps "What's the most crucial issue when deciding if Senator Cruz's citizenship makes him eligible for the Presidency?") is "What does the phrase 'natural born citizen' mean in context of Article II, Section 1 of the US Constitution?"
(*) Which may mean that he hasn't been a citizen his whole life, using a Cruz definition for when life begins. That's a separate discussion, though, and not very relevant to this one.