Michael Quinion says "It’s first recorded in 1824, but is probably much older".
An "origin" and definition of this "quaint phrase" are offered by the June 3, 1837 Niles' Weekly Register:
"Talking turkey" The Oneida (N.Y.) Democrat gives the following as the origin of this quaint phrase:
"Talking turkey," "as we understand it," means to talk to a man as he wants to be talked to, and the phrase is thus derived. An Indian and a white man went a shooting in partnership and a wild turkey and a crow were all the results of the day's toil. The white man, in the usual style of making a bargain with the Indian proposed a division of the spoils in this way: "Now Wampum, you may have your choice: you take the crow, and I'll tale the turkey; or, if you'd rather, I'll take the turkey and you take the crow." Wampum reflected a moment on the generous alternative thus offered, and replied - "Ugh! you no talk turkey to me a bit."
This is repeated partially word-for-word in the July 1, 1837 New York Mirror: Devoted to Literature and the Fine Arts, and they add that it is a "colonick phrase":
TALKING TURKEY. - The exact signification of this colonick phrase has recently been discussed by some of our contemporaries and has been finally settled by the Oneida Democrat which gives an account of its origin. An Indian and a white man went a shooting in partnership, and a wild turkey and a crow were all the result of the day's toil. The white man in his usual style of making a bargain with the Indian, proposed a division of the spoils in this way:- "Now, Wampum, you may have your choice, you take the crow and I'll take the turkey, or if you d rather, I'll take the turkey and you take the crow." Wampum reflected a moment on tho generous alternative thus offered and replied - "Ugh! you no talk turkey to me a bit."
The same tale is repeated with a turkey and buzzards in 1844 and with a turkey and an owl in 1868. and in 1889 to talk crow "is the opposite of 'to talk turkey,' and means to talk to another's disadvantage." Most repeat the tale very closely, including the "Ugh!".
Strangely, 1889's Americanisms--old & new by John Stephen Farmer gives an opposing meaning for talking turkey:
To talk turkey. — To indulge in grandiloquent periods ; to use high-sounding words, when plain English would do equally well or better. An allusion to the manner in which the male bird spreads and plumes itself.
But most meanings around this time are to speak fairly and clearly. "To speak to the purpose, to speak with due regard to the other side."
Another definition gives a different meaning to the modern use. From 1859's Dicitonary of Americanisms. A glossary of words and phrases, usually regarded as peculiar to the United States by John Russell Bartlett:
The quoted text was printed in an 1835 edition of Atkinson's Casket.
So this is to talk in a silly manner, to talk nonsense, and gives an example of talking turkey when being polite. This is similar to and gives more information on what Quinion says of the original meaning: "To start with it meant to speak agreeably, or to say pleasant things".
This meaning is also defined in 1872's Americanisms: the English of the New world by Maximilian Schele de Vere:
However, Bartlet appears to have changed his mind by 1878. Unfortunately this is all I could get from the snippet:
Dipper, a vessel, and consequently the name of the constellation, is of course older than the Dictionary itself, and is in both senses a downright Americanism, but is now first noticed by Mr. Bartlett. In explaining the phrase to talk Turkey he abandons his former definition ...