For those who aren’t has informed about elven “death”. When they “die” the Elven spirit goest to a place called the Halls of Mandos. They stay there awhile and then are sent back with a body the same has before, and all their memories. At least that’s how I understand Tolkien’s idea. Now, men, hobbits and dwarves die in the normal sense of the world, and they do not go to the Halls of Mandos, but somewhere else (our heaven). Only two elves have died in this sense, Luthian and Arwen.
Gandalf is a spiritual being, as such he can go inbetween worlds wherever his journies and duties take him.

Legolas, son of Thranduil, bowed his head. His proud features raked by grief and despair. Beside him stood Galadriel, the only other elf left, besides the prince, who had been in Middle Earth during the War of the Ring. Cirdan, Elrond, Celeborn, Tharanduil, all had past through the doors to the Halls of Mandos. That wasn’t, however, where the two fair-haired elves stood with tears on their faces.

No, they stood beside a simple hill crested by a proud strong mallorn tree. The only hill in all of Valinor crested with white simbelmyne with a door barred and blocked leading inside. For in all the wide land of deathlessness this was the only place of death.

Bilbo had gone first, followed a few years later by Frodo. Sam had lasted long enough to plant the mallorn sapling, and Gandalf had found him dead beside it. A few years later, Gimli had been laid beside the hobbits. After Gimli’s burial Legolas had begun to understand something he’d caught a glimpse of when Boromir had fallen so long ago. All his long life he’d known that no matter what happened, he’d see his elvin friends again. They’d come back to him. Gimli, the others, they would never come back.

With the world changing, the powerful Galadriel had asked the Valar to bring the remains of the others in the War to Valinor, so that the elves would never forget even if men might. So, Orome journeyed to Middle Earth and brought back the others; Theoden, Faramir, Eowyn, Eomer, Boromir’s broken horn, Aragorn, Arwen, Pippin, Merry, even Rosie Cotton to rest beside Sam forever. Legolas hadn’t left the hill for very long after that.

Galadriel broke his silent musing; “There is rest for us, Legolas. Come with me to Halls of Mandos, release your grief and heal your pain. I, too carry grief for those who have gone. You aren’t the only one.”

Legolas just looked at the beautiful Queen, “The ones you’ve lost you can see again, save for Arwen and Luthian. I will never see them again, and even if I go to Mandos they will not be there. The fellowship is finally broken.”

“Yes, I hurt for Arwen’s death, and for Luthian’s also, but everything changes.”

“Except us,” Legolas answered, slight bitter, “ we stay the same.”

“Only if you don’t chose your path,” Galadriel answered, turning away.

Galadriel made the journey to Mandos soon after. Only Gandalf and Legolas was left, and even when Gandalf was around, he wasn’t the same person who had wondered Middle Earth for so long. Here he was Olorin the Maiar, far more powerful then an elvin princeling, and with a lot of work to do even now. Legolas felt sometimes, that Gandalf the White had vanished forever, until the day that the old Gandalf came for a visit.

Whether it was a few or a hundred years later didn’t matter, Legolas saw the old Gandalf walking with his white staff towards him down the road. He’d been keeping the weeds from the delicate white flowers that still grew upon the hill when he first noticed the wizard. He bowed slightly;

“Greetings, Olorin,” he said.

“Here I am Gandalf,” the wizard smiled slightly, though it was easy to see that he too felt grief. “Here I am always Gandalf. Though I must ask, Legolas, why do remain here, bound to your grief? There is plenty of work for you to do in the great cities, and the elves would understand. Why do you stay here?”

“I can’t abandon them. It’s the closest I can come to being with them,” Legolas answered, realizing the fact for himself has he said it. “Even if I go to Mandos, they wouldn’t be there, and I don’t have the blood of Luthien or Arwen in my veins to make the choice.”

“Then,” Gandalf answered, “you must prove that you deserve the choice. After all, Luthien didn’t really have the choice either. It was a gift, and do you remember why?”

“Both of them loved their husbands so much that they couldn’t be parted from them. They risked everything for Beren and Aragorn. Is my love for my friend’s any less because it is not man to woman?” Legolas asked. “If I could ask anything, I’d ask to see them one more time.”

Gandalf smiled and extended his hand, “There is no difference, Legolas. Not for those pure of heart who love without exception, and they’ve been asking for you too.”

For a moment, Legolas’ eyes meet with Gandalf’s in surprise and fear. Then he took the wizards hand and was drawn away through a glittering curtain to a land even greener then the Valinor. His eyes glistened with tears has he saw his friends, even valiant Boromir, hale and welcoming him as though none of their sorrows had ever happened.

Galadriel, a child-elf no more then a few summers old hummed as she climbed the Hill to play on the branches of the Mallorn tree. Her features clouded when she saw Legolas sprawled on the ground, fair eyes unseeing has the flowering blossoms gently rained down upon the delicate flowers. For a moment, her heart stopped with sorrow, then she saw the joy still on his face and wept with happiness. As she turned to tell the lords of the Elvin cities, her words strung back…
“Not even death can break the bonds of fellowship. All is set to rights.”