This article is from the alt.usage.english FAQ, by Mark Israel firstname.lastname@example.org with numerous contributions by others.
MWCD10 (1993) dates this expression 1983. But Merriam-Webster
has since discovered a much earlier use, in H. V. Morton's "In the
Steps of St. Paul" (1936). The passage reads: "To use such words
would have been equivalent to calling his audience 'slaves and
robbers'. But 'Galatians', a term that was politically correct,
embraced everyone under Roman rule, from the aristocrat in Antioch
to the little slave girl in Iconium."
Jesse Sheidlower of Random House sent me this citation from the
U.S. Supreme Court decision Chisholm v. Georgia (1793): "The
states, rather than the People, for whose sakes the States exist,
are frequently the objects which attract and arrest our principal
attention [...]. Sentiments and expressions of this inaccurate kind
prevail in our common, even in our convivial, language. Is a toast
asked? 'The United States,' instead of the 'People of the United
States,' is the toast given. This is not politically correct."