Of their fate after life the Elves know much, because of their long staying in Valinor and of what they learned there from the Valar. Concerning Men the most lore on their afterlife are speculations, since Men have never got in touch with the Valar in any greater degree.
The fate of the Elves: The Elves see themselves as two different parts: the Fëa (spirit) and the Hröa (body). The two parts are not bound to each other, but without the Hröa, the Fëa is powerless, and with no spirit, the body is dead and will soon dissolve. {1}
The life-span of the Elves is by nature the same as that of the world (although they are often called immortal, which is a totally different thing). But the Elves call earth "Arda Sahta", the Marred World. Within its borders, nothing can be uninfluenced by Melkor, and Elves and Men, who are made of Arda's matter, are all likely to suffer in some way. {2}
Thus the elvish Fëa tend to "consume" the Hröa, until all that is left of it is a vague shape and it is indeed indestructable. Also, the Elves may die of grief or wounds (but not by disease) and then the Fëa will leave the Hröa.
Then the "houseless" Fëa will be summoned to the Halls of Mandos, and it may go there of free will. Most Fëar do this, but those who has been influenced by Melkor and are corrupt often dread the punishment they will receive in Mandos and stay in Middle-earth, trying to take over some other Hröa that already contains a Fëa.
Those who follow the summons may, if they wish, be reincarnated in a new-born body, identical to the previous (or returned to their earlier body, if it is still intact; this is seldom the case). The others stay in Mandos until the end of the world, or may go and live in Valinor. For the Elves are bound to the world, and can't leave it. In this their fate differs from that of Men.
All Fëar, whatever way they choose, must wait in Mandos for a time; how long depends on the invidual. If the Fëa has done evil in its previous life it must often wait longer until allowed to return to life. Sometimes it has to stay for good. Fëanor was for instance never allowed to leave Mandos. {3}
The reborn Elf is in all ways a child again, and does not remember its previous life until its experience and knowledge has grown. Then its life becomes double rich, since it has experienced two childhoods and has memories from two lives.
There are few cases where an Elf has been reincarnated more than once. The reason for this is unknown {1}. There are no documented examples of reincarnated Elves except Glorfindel of Gondolin who was reborn in the Second Age and helped Frodo and company to Rivendell.
The fate of Men: Men are not, contrary to the Elves, "bound to the world". They have by Eru been granted a special gift: death. When Men die, they go to the Halls of Mandos but do not stay there for long. They proceed away from the world and leave its borders, to which fate no-one knows. This has become a dread among Men, since they don't know what will follow. But this is a dread brought to them by Melkor, and the Elves, who are doomed to live on until the world ends, can't understand this fear of Eru's gift.
Some Men claim that they are not mortal by nature, but that it has been caused by Melkor. (The Elves, though, don't beleive this, since they don't think Melkor has the power to change the fate of a whole race.) This is based on the following old legend that can be considered the story of the "fall" of mankind.
Before any Men had yet died, Eru spoke to them and told them he would watch over them and help them if they needed him. But when they later asked him things, he would more often urge them to find the answers for themselves and enjoy the finding.
Then Melkor appeared among them in a beautiful shape and told them that he would help them and give them much knowledge if they took him to lead them. He gave them many gifts and tought them much lore and they would start fearing for a life without him. Then they spoke of Eru, whom they had only heard as a voice. But this made Melkor wrathful, and he said Eru was the Darkness that wished to devour them. Then he went away.
After a long time of grief and poverty, a darkness came over the world and blotted out the sun. Then Melkor came back shining like a torch, and all Men bowed before him. They built a temple for Melkor, and swore him their service. A long time they served him, but now he rarely gave out gifts or advice, or they had to pay for it with a gift or some evil deed. Eru didn't speak to them again, but once, when he said Men had abandoned him: but they were still his subjects. Therefore he would shorten their lives, and let them come to him and learn who was their true lord.
After that, some started dying, and Men went to Melkor for help. But Melkor did not hide his plans any longer. He told them that they should obey him or he would slay them. In time he started rewarding those that served him the best, which often were those who were the most cruel to others. Some Men started talking against him openly, but those he let put to death by fire in his temple. The legend ends saying that some Men flew and came to the sea, and found the Enemy there before them. {4}
Hypertextual System by FMI Publishing, 1995