The Facts on File Dictionary of Proverbs has the following (emphasis mine):
talk is cheap: [...] "What can you do?" "Go out Montana, just as soon as the weather is fit, and relocate the mine..." "Talk is cheap, but it takes money to pay for railroad tickets, went on Malone" (Horatio Alger, Joe the Hotel Boy, 1906) The proverb was first recorded in its current form in 1843 (T.C. Haliburton, Attaché), but the sentiment it expresses is of earlier origin.
Here is the relevant quotation from Haliburton's book, completely titled The Attaché; or, Sam Slick in England, and courtesy of Project Gutenberg:
"Minister," said Mr. Slick, "come, cheer up, it makes me kinder dismal to hear you talk so. When Captain McKenzie hanged up them three free and enlightened citizens of ours on board of the—Somers—he gave 'em three cheers. We are worth half a dozen dead men yet, so cheer up. Talk to these friends of ourn, they might think you considerable starch if you don't talk, and talk is cheap, it don't cost nothin' but breath, a scrape of your hind leg, and a jupe of the head, that's a fact.
Haliburton was a novelist, and Sam Slick seems to have been his primary literary foil, much like Hercule Poirot and Tom Ripley became for Agatha Christie and Patricia Highsmith, respectively. From Wikipedia (emphasis mine):
Sam Slick was a character created by Thomas Chandler Haliburton, a Canadian judge and author. With his wry wit and Yankee voice, Sam Slick of Slicksville put forward his views on "human nature" in a regular column in the Novascotian, beginning in 1835. The twenty-one sketches were published in a collection titled The Clockmaker, or the Sayings and Doings of Samuel Slick of Slicksville, First Series in 1836, supplemented by an additional 12 unpublished or new sketches. The book was Canada's first international bestseller and was hugely popular, not only in Nova Scotia but also in Britain and the United States....Slick’s wise-cracking commentary on the colonial life of Nova Scotia and relations with the U.S. and Britain struck a note with readers, leading to a second series in 1838 and a third in 1840.
The opening paragraph from a biography of Haliburton, titled Inventing Sam Slick: a biography of Thomas Chandler Haliburton, gives one a clue to Slick's renown:
For fifty years after 1837, Sam Slick the Clockmaker was the most
celebrated literary Yankee of the day. The mere mention of him
brought smiles to the faces of readers in Victorian Britain.
He struck the funny bone of a nation with his barrage of Yankee slang.
Few readers knew that his creator, Thomas Chandler Haliburton,
was a gentleman, a Judge of the Inferior Court of Common Please
in the colony of Nova Scotia. Today, Sam Slick is still more famous
than his creator.
So our best guess should be that the sentiment talk is cheap spread in its current form as a result of being associated with a long past literary phenomenon in Sam Slick, whose turn of phrase — perhaps even including talk is cheap — seemed to have delighted those over the pond.