Early Elephind newspaper database matches for the phrase
An Elephind newspaper database search turns up one stray instance of the expression from 1866 and one instance that appeared in four different newspapers from July through November 1895. Here are the seven earliest unique matches, in chronological order.
From "The Killing of John Counts, Alias Dawkins, a Freedman," in the [Columbia, South Carolina] Daily Phoenix (August 9, 1866):
On Sunday morning, a little freedman, residing at Mr. John A. Smith's, some three miles above the city, told him that two colored men had met him, near the branch, (which I but a short distance from Mr. Smith's residence,) and asked him to show them the nearest way to the Charlotte railroad, which he did. One of them had a bag of money, and gave him twenty-five cents in silver for his trouble. The other had two pistols. The little fellow asked the man where be got so much money. He replied: "That is for me to know and you to find out." He showed them on, through the salt-petre farm, and then returned home and gave the information.
From W.J. Lampton,"A Mountain Courtship: Just How Susan Stebbins Was Won by the Homliest Man on the Lick," in the Indianapolis [Indiana] News (July 5, 1895), reprinted from the New York Sun:
"'I s'pose,' says I, 'that you don't keer ef I stop and talk to you fer a minute, do you?'"
"'I ain't keerin' what you do,' says she, kinder sullen.
"'You look like you wuz expectin' somebody yourself,' says I, feelin' ez ef I'd like to choke whoever the feller wuz.
"'That's what,' says she, and I felt more'n ever like chokin' somebody.
"'Who is it?' says I, watchin' the streaks uv a laugh 'round her mouth and eyes.
"'That's fer me to know and you to find out,' says she, laughin' right out.
This same story (under the title "A Mountain Idyl") also ran in newspapers in Princeton, Minnesota (October 3, 1895), Des Moines, Iowa (October 11, 1895), and Grand Marais, Minnesota (November 9, 1895).
From W.T. Burrows, "Was Out of Balance," in the [Opelousas, Louisiana] St. Landry Clarion (August 4, 1900):
"I say, Fred, come here and see what I have fallen heir to." This as the first thing that greeted his [Fred Bronson's] ears on the morning after the fight with the cash balance, and as he followed his wife into the parlor of their home he was amazed to see on the parlor floor a beautiful rug that had not been there the day before.
"Why, where did you get this, my dear?" he asked.
"That, sir, is for me to know and you to find out," she answered, with a mischievous twinkle of her eyes.
From Bide Dudley, "Real News About Real People," in the [New York] Evening World (April 7, 1921):
Hob Jackson, a father, stuck his head into the parlor of his mansion on Main Street, his feet remaining in the hall.
"Ellie!" he called to his beautiful daughter.
"Oh, what the devil do you want?" he replied sweetly.
"Are the Count in thar7"
"That's for me to know and you to find out."
Bang! The door slammed, but trouble was in the air.
And from Max Shulman, "On Campus with Max Shulman," in the [Houston, Texas] Thresher (March 25, 1955):
Dr. Willard Hale Sigafoos, head of the department of anthropology at Southern Reserve University and internationally known as an authority on primitive peoples, returned yesterday from a four year scientific expedition to the headwaters of the Amazon River. Among the many interesting mementos of his journey is his own head, shrunk to the size of a kumquat. He refused to reveal how his head shrinking was accomplished. "That's for me to know and you to find out," he said with a tiny, but saucy grin.
Early Google Books database matches for the phrase
The earliest Google Books match for the phrase is from an unidentified story in Godey's Magazine (1881) [combined snippets]:
"You may trust me, sir. I know the police are after him with a sharp stick ; but I'll throw them off the scent if you give the word, and back it up with a pile of the shiners."
"How will you accomplish it?" questioned Breysdel, doubtingly.
"That's for me to know, and you to find out, your honor; but I know some of the dodges of the gentry, I do. What'll you give?"
"Five of the coins, besides those already promised you for the return of the child."
Godey's Magazine (also known as Godey's Lady's Book) was published in Philadelphia, Pennsylvania.
From unidentified court testimony in Documents [of the Massachusetts General Court] (1883) [combined snippets]:
Q. Where were you from the 15th of July, 1880, to the time you went to Danvers? A. Attending to my business.
Q. Where? A. In different places.
Q. Name one? A. Well, Lynnfield.
Q. Any other? A. Yes, wherever I chose to go.
Q. Where did you choose to go? A. That is for me to know, and for you to find out.
And from an unidentified story in Munsey's Magazine (1921) [combined snippets]:
"You asked me a little while ago if I was in this city at the hour when the crime was committed. I answered that it was for me to know and for you to find out. I'll answer direct now, just to stop this absurd suspicion which has been directed against me: I was not in the city at that hour, or within six hours of midnight. I was in Nashville."
Munsey's Magazine (originally Munsey's Weekly) was published in New York City.
Conclusions
All of the examples cited above—which range in publication year from 1866 to 1955—use the phrase "that's for me to know and you to find out" (or a close variant) in a very modern way—as a snappy retort to someone who is being inappropriately nosy or who is simply being naturally curious but whose question has prompted a dismissive or teasing response from the speaker.
All of the nineteenth-century instances seem to be from the United States, which provides at least a circumstantial case for its having a U.S. origin. The 1866 instance is attributed to a Black speaker, but the subsequent instances show no signs of involving African-American speakers.