They each had different reasons, which Tolkien discusses in his Letters.
Gandalf
As he himself notes in Return of the King, with Sauron defeated his role in the world is at an end:
Do you not yet understand? My time is over: it is no longer my task to set things to rights, nor to help folk to do so.
Return of the King Book VI Chapter 7: "Homeward Bound"
And as Tolkien writes in Letter 181 that he was simply returning home after his long labours:
Gandalf was returning, his labour and errand finished, to his home, the land of the Valar.
The Letters of J.R.R. Tolkien 181: To Michael Straights (draft). 1956
Elrond and Galadriel
In Letter 181, Tolkien writes that, with the diminishment of the Three and the undoing of their preservatory works, they had nothing left for them in Middle-earth:
[W]ith the downfall of 'Power' their little efforts at preserving the past fell to bits. There was nothing more in Middle-earth for them, but weariness. So Elrond and Galadriel depart.
The Letters of J.R.R. Tolkien 181: To Michael Straights (draft). 1956
Galadriel, specifically
It's worth noting that Galadriel wasn't staying in Middle-earth for her health; according to Letter 297, she was actually forbidden from going over the Sea (emphasis his):
The Valar listened to the pleading of Eärendil on behalf of Elves and Men (both his kin), and sent a great host to their aid. Morgoth was overthrown and extruded from the World (the physical universe). The Exiles were allowed to return — save for a few chief actors in the rebellion of whom at the time of the L[ord of the ] R[ings] only Galadriel remained.
The Letters of J.R.R. Tolkien 297: To Mr. Rang (Draft). August 1967
In a footnote to this letter, Tolkien mentions that this ban was lifted by the Valar, as a reward for her aid against Sauron (emphasis his):
At the time of [Galadriel's] lament in Lórien she believed [her ban] to be perennial, as long as Earth endured. Hence she concludes her lament with a wish or prayer that Frodo may as a special grace be granted a purgatorial (but not penal) sojourn in Eressea, the Solitary Isle in sight of Aman, though for her the way is closed. (The Land of Aman after the downfall of Númenor, was no longer in physical existence 'within the circles of the world'.) Her prayer was granted – but also her personal ban was lifted, in reward for her services against Sauron, and above all for her rejection of the temptation to take the Ring when offered to her. So at the end we see her taking ship.
The Letters of J.R.R. Tolkien 297: To Mr. Rang (Draft). August 1967
This is echoed in broad strokes in Letter 320, though with the added detail that Galadriel refused forgiveness at the end of the First Age:
Galadriel was a penitent: in her youth a leader in the rebellion against the Valar (the angelic guardians). At the end of the First Age she proudly refused forgiveness or permission to return. She was pardoned because of her resistance to the final and overwhelming temptation to take the Ring for herself.
The Letters of J.R.R. Tolkien 320: To Mrs. Ruth Austin (excerpt). January 1971
Frodo
Arwen interceded on his behalf; she argued that because his suffering and her decision to become mortal were part of the same Divine Plan, he should be eligible to go to the Undying Lands in her place:
It is not made explicit how she could arrange this. She could not of course just transfer her ticket on the boat like that! For any except those of Elvish race 'sailing West' was not permitted, and any exception required 'authority', and she was not in direct communication with the Valar, especially not since her choice to become 'mortal'. What is meant is that it was Arwen who first thought of sending Frodo into the West, and put in a plea for him to Gandalf (direct or through Galadriel, or both), and she used her own renunciation of the right to go West as an argument. Her renunciation and suffering were related to and enmeshed with Frodo's: both were parts of a plan for the regeneration of the state of Men. Her prayer might therefore be specially effective, and her plan have a certain equity of exchange. No doubt it was Gandalf who was the authority that accepted her plea.
The Letters of J.R.R. Tolkien 246: To Eileen Elgar (drafts). September 1963
Bilbo
Gandalf gave him permission, and did so for two reasons:
- He liked Bilbo
- Frodo needed a hobbit companion in the Undying Lands, to help stave off madness:
Bilbo went too. No doubt as a completion of the plan due to Gandalf himself. Gandalf had a very great affection for Bilbo, from the hobbit's childhood onwards. His companionship was really necessary for Frodo's sake – it is difficult to imagine a hobbit, even one who had been through Frodo's experiences, being really happy even in an earthly paradise without a companion of his own kind, and Bilbo was the person that Frodo most loved.
The Letters of J.R.R. Tolkien 246: To Eileen Elgar (drafts). September 1963
Sam
We're never actually told why; we just know that he did.
One plausible reason is that, Bilbo presumably being dead by this point, Frodo was in need of a new companion. Since he was still a Ringbearer, however briefly, Sam, in his advancing years, may have found himself in need of some of the healing Frodo went in seek of. But that's all speculation.