Learn English – the origin of the phrase “Eastern Seaboard”

The rhetorical, as opposed to etymological, origin is the device known as paralpsis, paraleipsis, paralepsis, (also praeteritio) meaning pretended omission for rhetorical effect, because in saying we won't mention X, of course we just did.

Edit (by FumbleFingers): A later question on the same topic gives the relevant word as apophasis. It's a little hard to see from this graph, but what it shows is that until recently, the combined total written instances for various spellings paralpsis, paraleipsis, paralepsis dwarfed those of apophasis. But the graph from 1970 on shows apophasis is now overwhelmingly more common. I don't think this means the correct term for this rhetorical device has just changed - it's just that the theological use of apophatic has led to it being more commonly known, and used "metaphorically".

Results from a Google Books search strongly suggest that the expression originated (in print) in religious publications. At least in my search results, publications of the missionary wing of the Methodist Episcopal Church account for the first five matches, spread across a period of seven years. The earliest of these sources (from January 1910) credits the saying to a Commissioner McFarland, who may be the author of the third article cited below.

From "Never Paralleled in New York," in The [New York] Christian Advocate (January 20, 1910):

Many ministers have heartily indorsed the [Laymen's Missionary] Movement and will support it with their indispensable influence. With their cooperation failure is impossible, and it is the universal post-convention report from the other cities that all local causes have been helped on by the new impulse of the Movement whose watchword is "For the Other Man." As Commissioner McFarland said at the Astor dinner, The rising tide lifts every boat!

From "Japanese Church in Wonsan, Korea," in The [Nashville, Tennessee] Missionary Voice (May 1911):

Now the building of the church in Wonsan [Korea], of course, was not entirely, or maybe even mainly, responsible for the building of the great church at home. But at least it did not hinder, and who doubts that the enlargement of heart that came to them through that unselfish thing, the spiritual swing developed in that enterprise abroad, hastened and helped on the larger thing they would do at home? "The rising tide lifts all boats," and "the light that shines farthest shines brightest at home."

From Henry B. F. McFarland, "The Man by Man Rise of a Race of Men," in Association Men (January 1915):

The rising tide lifts all the boats upon it. All parts of the colored [Young Men's Christian] Association movement have shared in the new progress. Great corporations employing negro workmen—like the Newport News Ship Building Company, which has already started work, with its four thousand negro employees—see the advantage of such Associations.

From "Woman's Home Missionary Society," in Minutes of the One Hundred and Seventeenth Session of the New York Conference of the Methodist Episcopal Church held in First Church, Peekskill, N.Y. March 22, 1916 (1916):

Wherever there is an active, interested, wide-awake Woman's Missionary Organization there will be found a broadened vision, an increasing zeal along all lines, and a permeating spirit of the Christ-love that is most helpful. "The rising tide lifts all boats."

From Hugh Burleson, "The Progress of the Kingdom," in The Spirit of the Missions (May 1916):

The editor of THE SPIRIT OF THE MISSIONS is certain that he speaks not only for himself but for every official connected with any missionary enterprise when he declares that he would not, if he could, divert a single dollar from the relief of Europe. On the contrary, he rejoices when gifts for the war sufferers increase, not only because of his passionate desire that this awful suffering may be relieved, but also because he knows that "a rising tide lifts all the boats," and that every good cause should profit by the sympathy which this crying need awakens in the hearts of men and women who too long have been concerned chiefly about their own comfort and gratification.

From "A Hint from Harvard," in Harvard Alumni Bulletin (December 11, 1919):

There must be hundreds of Harvard men who on reading that [story] will directly double their subscriptions; the tale is so darned humane! I am not a Harvard man as you know, but the Top Sergeant and his wife make me double my paltry ten dollars. The psychology of the outsiders with colleges of their own to serve is quite correct. A rising tide lifts all the boats!

And finally, the cover of American Gas Monthly (March 1920) consists of the following quotation and subtitle:

"The Rising Tide Lifts All the Boats."

When the tide of public opinion swells through recognition of service well performed, all our boats will be lifted.

Basically what we have here is a slogan so successful that in a single decade it went from being a watchword—indeed almost a catchphrase—of a vigorous Christian missionary movement to becoming an inspirational proverb for members of the American Gas Association to contemplate.