The following is what Safire had to say (January 1, 2006):
Not content with his allusion to rhetorical jawboning, Lieberman went on to say that in matters of war, "Politics should stop at the water's edge."
I had what I thought was the source of that metaphor of nonpartisanship in my political dictionary: Sen. Arthur Vandenberg, R-Mich., said in 1950, "To me 'bipartisan foreign policy' means a mutual effort under our indispensable two-party system to unite our official voice at the water's edge."
The historian Richard Neustadt wrote a few years later that President Harry Truman played chief of foreign policy "like a career official anxious to obey his own injunction that 'politics stops at the water's edge.'"
Vandenberg, who courageously went up against his party's isolationists, has been getting credit for that felicitous phase for years.
Sorry, Arthur, it wasn't your coinage, and leafing through musty books and records is no longer the way for etymologists to go.
The Little Search Engine That Could huffs and puffs through mountains of data to reveal that on Jan. 17, 1907, The Washington Post reported that at a banquet in D.C. honoring Secretary of State Elihu Root, President Theodore Roosevelt said that once in office, a public official -- whatever party he belonged to-- "must feel that he is the servant of the people. This is true of all public officials, but perhaps it is in a special sense true of the secretary of state, for our party lines stop at the water's edge."
Here is the list of WATER'S EDGE quotes I dredged up, which helped me form my opinion of what I believe the term means:
Ken G – January 19, 2005<1961 “As well as any alliance in human history, the Western Allies have realized that politics does not stop AT THE WATER’S EDGE, that the national interests of the one must be accommodated to the national interests of all.”—‘Time Magazine,’ 27 October>
<1965 “‘We mean to show that this nation's dream of a Great Society does not stop AT THE WATER’S EDGE,’ he said. ‘It is not just an American dream.’ Johnson pointed out that nearly 50% of all nations have populations that are 50% or more illiterate. Said the President: ‘Unless the world can find a way to extend the light, the force of that darkness may engulf us all.’”—‘Time Magazine,’ 24 September>
<1993 “It may be that Clinton's foreign and defense policy team is second-rate, judging from its performance in Somalia. Or it may be that a President whose interest flags AT THE WATER EDGE is simply a slave to public and congressional opinion when he lacks his own clear bearings.”—‘Time Magazine,’ 18 October>
<1998 “‘Sooner or later, terrorists will realize that America's differences end AT THE WATER’S EDGE.’ said none other than Jesse Helms, ‘and that the United States' political leadership always has, and always will, stand united in the face of international terrorism.’ Nice to know bipartisanship is still out there somewhere.”—‘Time Magazine,’ 20 August>
<1999 “There may have once been a time when politics stopped AT THE WATER’S EDGE, but today it scarcely taps the brakes. 
<2000 “It used to be that foreign affairs and national security were taboo topics for partisan potshots. Not this year; instead of stopping AT THE WATER’S EDGE, politics in Washington is plunging off the deep end.”—‘Time Magazine,’ 18 September>
<2003 “Sure, Democrats are testing the old Cold War rule that politics should stop AT THE WATER’S EDGE, but Republicans are doing more than charging the Left is gauche. The GOP campaign is itself political. Party members are making such a public fuss in the hopes of de-legitimizing all Democratic criticism of Bush’s handling of the war on terror.”—‘Time Magazine,’ 15 September>