The word native derives from the Latin word verb nasci, which means to be born. So if native means born in a place, what is the need for native-born?
"Garner's Modern American Usage" says this of the phrase native-born citizen:
This phrase, though it has been fairly common since the 19th century, reeks of redundancy.The phrase is, however, used quite often in print. A Google News search turned up the phrase in 404 postings, including on such reputable news sites as the Dallas Morning News, The New York Times, Forbes and The Washington Post. (Full disclosure: A Google search of the Web site of the newspaper at which I work came back with 134 hits, though many of them are Associated Press stories.) A glance through the LexisNexis database turned up 751 mentions of this phrase in the last six months, though many of these appeared to be letters to the editor, too.
One reason this phrase seems to be used is to avoid any confusion that could arise between a native American and a Native American, though AP style does call for using American Indian when referring to the indigenous persons.
There is a way to write around the confusion, though it adds a handful of characters. Instead of a native-born Mexican-American (yes, this did come up on a Google News search), which is redundant, you could use native Mexican-American. However, this does not, in my mind, clearly state where this person was born. There are a lot of assumptions to be made with good arguments on both sides. But why not write Mexican-Americans born in the United States? It's descriptive, accurate and not redundant.