A wizard did it
Tolkien's conception is illuminated a little in his Letter 246 (September 1963), where he has an aside to talk about Frodo taking Arwen's place. With my emphasis:
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 Appendices show clearly that he was an emissary of the Valar, and virtually their plenipotentiary in accomplishing the plan against Sauron. He was also in special accord with Cirdan the Ship-master, who had surrendered to him his ring and so placed himself under Gandalf's command. Since Gandalf himself went on the Ship there would be so to speak no trouble either at embarking or at the landing.
This is enough explanation for the ship carrying Bilbo, Frodo, and Galadriel. Gandalf was aboard in his capacity as victorious emissary of the Valar. His will was aligned to theirs and so he would "know" that this was the right thing to do. (And it is not a matter of communicating with them in advance in order to gain permission; Gandalf himself is already the messenger.)
While Galadriel was very well-informed, it is not obvious whether she shared this confidence. After her mirror confrontation where she declares that she "will go into the West", she still sings a lament that a ship may not come for her: so her rejection of the Ring was not decisive. The defeated Saruman later taunts her using the same words:
"And now, what ship will bear you back across so wide a sea?" he mocked. "It will be a grey ship, and full of ghosts." He laughed, but his voice was cracked and hideous.
I think that Saruman had an awareness that she would indeed be allowed to return, but for him that is twisted into bitterness. This is similar to other classic portrayals of a fallen angel as someone who still knows a lot about God, but doesn't like it. (Compare Thomas Aquinas in Summa Theologiae Iª q. 64 a. 1 co., saying that the demons retain a degree of angelic knowledge concerning higher things, but are "utterly deprived" of love and the wisdom that comes from it.)
As to Sam and Gimli, whose journeys are described in LotR Appendix B as respectively "the tradition is handed down" and "it is said", we can only speculate that they left in the hope that they would be received. Frodo and Sam share a conversation in the final chapter where this seed is planted:
"Where are you going, Master?" cried Sam, though at last he understood what was happening.
"To the Havens, Sam," said Frodo.
"And I can't come."
"No, Sam. Not yet anyway, not further than the
Havens. Though you too were a Ring-bearer, if only for a little while.
Your time may come. Do not be too sad, Sam. You cannot be always torn
in two. You will have to be one and whole, for many years. You have so
much to enjoy and to be, and to do."
At this point, Frodo has certainly been told all about the plan, and he would not have raised the possibility with Sam as a careless remark. He is speaking with wisdom and it appears that although he lacks Gandalf's explicit authority, he has some insight into the workings of this particular grace. On the pure logistics level, as Sam set sail from the Havens, it may be that Cirdan or other elves there had been notified by Gandalf that Sam would turn up one day, and to let him on board. But there is nothing textual here and I am interpolating based on the references in Letter 246 to Gandalf's influence being needed at embarkation - equally possible that an elderly, stubborn Sam just said "I'm going and that's that" and the elves conceded.
For Gimli, all we have is the following from the end of Appendix A (quoted by @Mustapha Mond in comments), suggesting that some "authority" might have been wielded by Galadriel herself:
We have heard tell that Legolas took Gimli Glóin's son with him because of their great friendship, greater than any that has been between Elf and Dwarf. If this is true, then it is strange indeed: that a Dwarf should be willing to leave Middle-earth for any love, or that the Eldar should receive him, or that the Lords of the West should permit it. But it is said that Gimli went also out of desire to see again the beauty of Galadriel; and it may be that she, being mighty among the Eldar, obtained this grace for him. More cannot be said of this matter.
