The strict answer is no. You don't have to be born IN America. But you do have to be a citizen and that is different. You can be born outside the US to a US mother. Being born outside the US from a US father seems to be unresolved (which seems to me to be a slightly irrational distinction). But in any uncertainty, The Supreme Court would decide.
Certainly American territory counts as far as the place of birth goes -- Barry Goldwater was born in the Arizona Territory, three years before Arizona became a state. John McCain was born in the US-controlled Panama Canal Zone. Neither was ineligible to run, even though neither won. There doesn't appear to be a case of a successful presidential candidate born in a territory rather than a state.
The first ten presidents, of course, were born before there was a United States to be born in.