Taking my cue from Josh61’s helpful comment (which has since become a full-fledged answer), I revisited The Clockmaker (1839), and found that it offers an explanation of the phrase’s literal and figurative meaning, in a dialogue between Sam Slick and a Scot of the border country, immediately after Slick has stretched out the fingers of his right hand “until they represented the radii of a circle” and then “applied the thumb to the extremity of [his] nose, in a horizontal position”:
“Did you ever see the like o’ that,” said the puzzled Scot to himself, “and wha is he?” “A wrinkle on the horn,” said I, again applying the thumb to its old signal-staff, the nose, “and I thank you for the hint.”
“A wrinkle on the horn?” slowly repeated my astonished companion; “puir body, he is daft, as sure as the world.”
“No, my man,” said I, “not daft, but wiser. In America, for you must know I come from that far-off country, we tell the ages of our cattle by examining their horns, at the root of which, at the end of three years, there appears a small ring or wrinkle, and each succeeding year is marked by another. This has given rise to a saying, when a man acquires a new idea, that he has got ‘another wrinkle in his horn,’—do you take?”
The "horn" in the first paragraph is slang for nose, but Slick soon connects that notion of horn with the actual cow's horn he mentions later in the dialogue. Also from The Clockmaker:
P.S. — l will give you a wrinkle on your horn that's worth havin'. Should our great gun be absent and you left in London, recollect we do as the British do, give no instructions we can help ; write what must be wrote so it will read any way, and leave subordinates to incur all responsibility of actin’ and readin’.
And from James Johnson, A Tour in Ireland (1844):
Then George Wynder, listen to me, remember what I say, and I will put another wrinkle in your horn.
A much later match appears in the Staunton [Virginia] Spectator (February 20, 1895):
A certain good church brother in speaking of the prosperity of a nearby neighbor of his, said: "He has twenty-five hens, and gets from 3to 4 dozen eggs per day." The crowd wondered if some of the hens produced 2 or 3 eggs per day, or how, but no one asked him to explain, and be went his way in all his glory, while the crowd unanimously accorded him another wrinkle in his horn.
A search of the Library of Congress site turns up numerous mentions of wrinkles in horns and (sometimes) indications of their meaning. For example, from another adventure of Sam Slick, reprinted in the Maumee [Ohio] Express (March 17, 1838):
Now says the Major, I’ll give you, Slick, a new wrinkle on your horn. Folks aint thought nothin of, unless they live at the Treemomnt [sic] ; its all the go. Do you dine at Peep’s tavern every day, and off hot foot to the Treemont, and pick your teeth there on the streets steps, and folks will think you dine there.
From a poem titled “The Old Cow” in the [Edenton, North Carolina] Fisherman & Farmer (March 29, 1889):
I look at you with sad regret
And mourn to think we ever met;
For every wrinkle in your horn
Proclaims of wasted hay and corn.
From the Monroe City [Missouri] Democrat (February 12, 1903):
St. Louis has added another wrinkle to its horn of prosperity by becoming the great coon skin market of the world.
And from the “Out of the Ginger Jar” column in The Adair County [Kentucky] News (December 7, 1910):
Mr. Cityman is hereby informed in response to his Inquiry, that the wrinkles on a cow’s horn are not caused by trouble or worry.
Stepping away from Google Books and into the turmoil of CattleToday.com’s Q&A Boards, I encountered this posting dated December 28, 2005, by a participant named Caustic Burno, from the Big Thicket area of East Texas:
No Dun we have just been over some of the same rough trails puts a wrinkle in your horn makes you remember.
So it appears that equating wrinkles in a horn with experience and acquired wisdom remains current in at least one part of the United States.
I haven’t been able to find any earlier references to putting a wrinkle on one’s horn than those in Halliburton’s Sam Slick stories of 1838, but I suspect that as a folk expression it goes back considerably farther than that.
Addendum (July 5, 2018)
Rural awareness that cows add a new wrinkle to their horns each year is probably ancient. Notice of it appears in "An Essay on a Registry for Titles of Lands" in A Collection of State Tracts, Publish'd During the Reign of King William III, volume 2 (1706):
I have seen an original Mortgage of one Skin [that is, sheet or page], bred up by a Scrivener (in six Years) to one and twenty, by assigning it to every Year, and adding one Skin to every Assignment by Recitals and Covenants. As Cows after three Years old, have one Wrinkle added to each Horn for every Year after, which shews their Age: And I am inform'd that one Deed of sixty Skins was heav'd out of a Conveyancy Office the other day.
William III reigned from 1689 to March 8, 1702, so at the latest this essay dates back to the earliest years of the eighteenth century.
Clearly, there was ample time for "put a wrinkle on one's horn" to emerge as a metaphorical folk saying, as it appears to be in the review of two books on the subject of fever in The Medico-Chirurgical Review, and Journal of Practical Medicine (February 1830), cited in Mari-Lou A's excellent answer:
As soon as the mornings get a little finer, and the evenings longer, we will invite Dr. Smith to a strict examination of a few patients at the Fever Hospital ; and if we find them presenting the same phenomena at these two periods, we shall cheerfully admit that the worthy author has added a wrinkle to the horn of our knowledge.