The more interesting story is that of Ted Cruz, who had a noncitizen father and was born in Canada.
https://travel.state.gov/content/travel/en/records-and-authe...
The arguments as I recall were basically two-fold: 1.) At the time, it was the Canal Zone (which wasn't quite US soil but maybe close enough) and 2.) There were some long-standing common law precedents related to agents of the king, diplomats, etc.
The only complicated area in law is when only a single parent is a US citizen and the child is born overseas. This was a consequence of the 20th century reality that the US had vast numbers of military personnel stationed globally.
This is why Obama, McCain and Ted Cruz are eligible for the Presidency
edit: doh. Forgot that Obama was born in Hawaii
This is incorrect. John McCain was born in a foreign country, but he was born to American citizen parents, which made him natural born anyway. Someone who was born to noncitizen parents, but born within the geographical US would also be considered natural born. The US definition of "natural born citizen" is a lot more flexible than what most countries will allow even for naturalized citizens.