How did Galadriel knew that Gandalf was back?

[Legolas]

Lovely quote/observation, Eol. It's also important to notice it includes Celeborn also.

Mae states

I don't believe it was Eru who sent Gandalf back, for two reasons. One, Manwe or another Vala would be perfectly capable of doing so, and as they were the ones who sent Gandalf over in the first place, it seems most likely they’d be the ones to send him back. Two, that would involve Eru directly interferring, for lack of a better word, in Arda. It's pretty debated as to whether he would do this or not, but the general idea is that he wouldn't, at least for something like this. (see the Athrabeth for more details there)

Eru did intervene directly in at least two instances - he sent a deceased Gandalf back into the world, and in the changing of Arda where it was made round and Aman was removed from the physical world.

Because of the nature of Gandalf's incarnation, he actually did die and left the world. His fea was bound to his hroa, and in the exhaustion and death of the latter, the former left. None of the Valar, even Manwe, could've brought Gandalf back. Obviously elves could be rembodied in the Halls of Mandos, but mortal men and Ainur who died left the world entirely. Tolkien explains Eru's intervention in Letter No. 156:

Gandalf really 'died', and was changed: for that seems to me the only real cheating, to represent anything that can be called 'death' as making no difference... He was sent by a mere prudent plan of the angelic Valar or govenors; but Authority had taken up this plan and enlarged it, at the moment of its failure. 'Naked I was sent back- for a brief time, until my task is done'. Sent back by whom, and whence? Not by the 'gods' whose business is only with this embodied world and its time; for he passed 'out of thought and time'. Naked is alas! unclear. It was meant just literally, 'unclothed like a child' (not disincarnate), and so ready to receive the white robes of the highest. Galadriel's power is not divine, and his healing in Lorien is meant to be no more than physical healing and refreshment.

I've boldfaced the most important parts of the quote. 'Authority' is indeed Eru.