There is a question that precedes this:
How did Frodo know he could sail into the West? The two questions are tied to one another, I believe.
On the way home from
Rivendell (
RotK, “Homeward Bound”), Frodo,
Gandalf,
Sam,
Merry, and
Pippin crossed the Ford of Bruinen on 6 October, a year from the day after Frodo was stabbed by the
Witch-king. Frodo was reluctant to cross the ford, and when Gandalf asked if he were in pain, he replied that he was, to which Gandalf answered that “some wounds … cannot be wholly cured.” Frodo complained, “Where shall I find rest?” but “Gandalf did not answer.”
At the end of the previous chapter,
Elrond quietly told Frodo, “[A]bout this time of the year, when the leaves are gold before they fall, look for
Bilbo in the woods of
the Shire. I shall be with him.”
Somewhere – I cannot find the citation tonight – I believe
Tolkien wrote that Frodo was told that he was welcome to accompany Gandalf and Elrond on the ship to Tol Eressëa. Bilbo was already bound for that voyage. I believe Tolkien says that this was conveyed to him in Rivendell during the two weeks Frodo and his companions were there, but again, I can’t find the passage tonight.
After that, Sam’s knowledge that he could also pass over the Sea to Tol Eressëa is easily understood. Frodo knew exactly when and where to meet Gandalf, Elrond,
Galadriel, and Bilbo: this knowledge was either given to Frodo in Rivendell or relayed to him by an
Elf or (less likely)
Dúnadan.
Sam expressed distress when he realized Frodo was also leaving with them. But he remained, as Frodo said, “solid and whole,” at least while Rose his wife lived.
Here I will depart from the written text a bit. I think there can be little argument that Frodo suffered what we now call “post-traumatic stress disorder” or PTSD. In World War II, it was called “battle fatigue”; Tolkien knew it in World War I as “shell shock”. I cannot see how Sam avoided this. I suspect his anchor was Rose, his beloved wife, and to a lesser extent his children, especially Elanor. When Rose died, Elanor was already married and moved to Undertowers in Westmarch. It was then that Sam, too, took leave of
Middle-earth: the woman he loved, who kept him “solid and whole,” was gone, and he, like Frodo, was in pain.
How did Sam know that he could go? I think that there can be little doubt that Frodo told him that he could, if he wished, follow Frodo into the West. I suspect this was also for the final healing of Frodo, who likely passed away among the
Elves in Tol Eressëa not long after Sam arrived.
It would be another sixty years before
Aragorn Elessar gave up his life. Then
Legolas constructed a white ship and, accompanied by his friend
Gimli, sailed into the West. By that time, I believe all three
Hobbits that had preceded them were dead. Gimli also died in Tol Eressëa: it was not Eldamar, on the mainland of
Aman, but still received some of the air of Middle-earth (
Silmarillion, “…the Hiding of
Valinor”: “all those of Elven-race … must breathe at times the outer air and the wind that comes over the sea from the lands of their birth…”).
In
Letter 246, Tolkien wrote that
Arwen developed this plan of replacing her with Frodo.
…Frodo was sent or allowed to pass over Sea to heal him – if that could be done,
before he died. He would have eventually to “pass away”: no mortal could, or can, abide for ever on earth, or within Time. So he went both to a purgatory and to a reward, for a while: a period of reflection and peace and a gaining of a truer understanding of his position in littleness and in greatness, spent still in Time amid the natural beauty of “
Arda Unmarred”, the Earth unspoiled by
evil.
And Sam was permitted to join him. How did he learn this? I think Frodo told him; but Sam was also in communication with, and often in physical proximity to Aragorn and especially Arwen, who could also tell him this.
Celeborn departed
Lórien and moved to Rivendell to be with his grandsons, Elladan and Elrohir; I suspect he could have conveyed this information, too, as perhaps could Elrond’s sons. Upon reflection, that Sam was be aware of his offer to go to the Uttermost West should come as no great surprise.