Let's do a little bit of sleuthing.

The source

As far as I can tell, there are three sources for this quote: one is "Waging peace and war: Dean Rusk in the Truman, Kennedy, and Johnson Years", by Thomas J. Schoenbaum (1988, p. 421), another is Rusk's autobiography "As I saw it" (1990, p. 271), and another is the transcript of an interview of Rusk by Schoenbaum, made circa 1985, which is likely to be the primary source. It can be listened to here (starts at 43:11)

Schoenbaum 1988

As usual when he crossed swords with de Gaulle, Rusk had difficulty. De Gaulle took the further step in 1967 of pulling France entirely out of the military arm of NATO, and when he told Rusk to his face that he wanted "every American soldier out of France," Rusk's anger and impatience boiled over, "Does that include the dead Americans in the military cemeteries as well?" he asked. De Gaulle fell silent, and Rusk felt a measure of satisfaction that he had at last gotten in one good lick at de Gaulle.

Rusk 1990

When President de Gaulle decided to quit NATO, President Johnson was determined to do everything that de Gaulle asked us to do, simply as a matter of dignity, and get out our forces out of France before the deadline. But de Gaulle's request went down hard in Washington. In fact, Johnson insisted that I ask de Gaulle, "Do you want us to move American cemeteries out of France as well?" I carried out my instructions. De Gaulle, very embarrassed, had nothing to say.

Rusk's verbatim circa 1985

DEAN RUSK: I don't think you ought to use this because it's a little out of taste, but I did fluster him on one occasion, on the personal instruction of President Johnson. This was after de Gaulle had ordered all American troops out of France: ordered NATO out of France. The next time I called on him after that I referred to this and on the personal instruction of President Johnson I said, "Mr. President, does that include American cemeteries?" And he was really flustered with that: really flustered. And he said, "Oh, no. No, of course not." But had we moved the American cemeteries out of France the French people would have come up with a roar. But that was, I think, the dirtiest question I ever had to ask anybody.

SCHOENBAUM: And Johnson put you up to that?

DEAN RUSK: Johnson told me to do it. (laughter)

As one can see, the stories are a little different. In Schoenbaum, the French president tells Rusks "to his face" that he wants to kick American soldiers out of France, and the Rusk blurts his answer in anger, happy to get in "one good lick". The red-blooded, patriotic American puts the arrogant, ungrateful Frenchman in his place. Rusk's own written version is more diplomatic. He makes clear that this was not his idea but Johnson's, and that he was just the messenger. In both written versions, the story ends here and there's no humiliated de Gaulle leaving the room. The transcript version is more or less the same as in Rusk's autobiography, but de Gaulle does not fell silent and actually answers Rusk.

All later retellings are more or less embellished versions of the tale, notably the Schoenbaum version. There's also a version where Johnson tells Rusk "Ask him about the cemeteries, Dean!" but I can't find a source for that.

The timeline

(FRUS refers to Foreign Relations of the United States, 1964–1968, Volume XIII, Western Europe Region, available here)

There have been many accounts of the French departure from NATO, but I'll use that of Alessandra Giglioli (1998) who won NATO fellowship for her work. The French had been thinking about pulling out of NATO for a while, at least since Spring 1965. The Americans knew it and prepared contingency plans accordingly (10 June 1965, Circular Telegram From the Department of State to the Posts in the NATO Capitals: "There have been repeated rumors that French may shortly ask US in effect to vacate certain military facilities in France", FRUS N°89). On 2 March, Rusk sent a telegram to the posts in NATO capitals that said (FR N°135):

While continuing firmly on our course in spite of President De Gaulle's views, we should lean over backward to be polite and friendly to France, to President De Gaulle personally, and to all French government officials. Backbiting, recriminations, attempts to downgrade the importance of France as a nation, or attempts at reprisals should be avoided no matter what the temptation. They cannot be effective, will only irritate President De Gaulle and make him more difficult to deal with, and are likely to cause French public opinion to rally to his side against the US. [...] If President De Gaulle insists on the removal of US forces from French soil, we should accede gracefully and should move promptly to consider repositioning our line of communications elsewhere. Attempts to dissuade President De Gaulle or to obtain various concessions would seem to be unwise, although it would be helpful if France would maintain the LOC in a caretaker status. If France should decide to pull out of any active role in NATO, we should not replace our NATO tie with France by any bilateral agreement. Any such agreement would make it much more difficult for France to return to the fold at a later date and might set a pattern that could undermine the whole NATO structure. In the event of a French withdrawal, we should support the continuation of the NATO organization without France.

On 7 March 1966, after weeks of teasing, de Gaulle wrote a letter to Johnson announcing the pull out and Johnson answered formally on 22 March (FR N°146). In the US, officials were more shocked by the "brutality" of de Gaulle's announcement than by the announcement itself. People like Rusk and Acheson were hardliners who wanted a "punitive" answer (Rusk had found France's attitude "outrageous" for a while, well before the NATO crisis, see FRUS N°46, 8 November 1964) but others, notably at the Pentagon, and Johnson himself, were more flexible. In his memoirs, LBJ says (Johnson, 1971):

The only way to deal with de Gaulle's fervent nationalism was by restraint and patience. To have attacked de Gaulle would only have further enflamed French nationalism and hurt French pride. As I told McNamara, when a man asks you to leave his house, you don't argue: you get our hat and go.

LBJ "viewed de Gaulle's actions as ill-considered and dangerous" (Johnson, 1971) but, by May 1966, he considered that France leaving NATO was a done deal and that attacking de Gaulle over it was unproductive (FRUS N°161):

I see no benefit to ourselves or to our allies in debating the position of the French government. That government has made known its position. Our task is to rebuild NATO outside of France as promptly, economically, and effectively as possible.

The US press was much less accommodating than the US administration, and there was a lot of anti-French resentment in the public opinion throughout 1966. Speaking of cemeteries, The Orlando Sentinel, 31 March 1996 ("Gen. de Gaulle devoid of gratitude") wrote:

But what will the proud president of France do about the American cemeteries in France, with their white crosses row on row? Will he now want to disturb the eternal sleep of the 60,000 young Americans who rest in the soil of France? Won't the graves of these heroes from across the sea serve to remind the haughty and ungrateful general of the unpaid, and unpayable debt his nation owes to America?

Still, for the Johnson administration, NATO could survive without France, de Gaulle would not be president forever, and there was no positive outcome for "a full-blown war with De Gaulle" (FRUS N°143).

On 16 December 1966, Rusk sent a telegram to Johnson from Paris (FRUS N°229):

I was glad to hear from Bob McNamara that you wanted to get as many of our people and as much of our equipment out of France as possible prior to De Gaulle's deadline. This seems to me to be the dignified attitude which we should take in the face of an outrageous decision taken without the slightest consultation with us.

To be continued below...