The concept of immortality in Arda is very complex, because it differs in nature between the races. Usually, however, it refers to the type of life possessed by the Elves, who do not have the inability to be slain, but rather the inability to age and die of disease (but see below).
The only truly immortal beings (in the sense that death or any loss of their being cannot be brought upon them) in Arda are the Valar and Maiar. Because they originally came from beyond Eä, nothing within its boundaries can hurt them. One reason for this is because their spirits do not need a body to be complete, unlike the Incarnates. The Valar and Maiar take visible form at will, and this form was said to be more like clothing than actual incarnation. Forcible removal of this "raiment" (such as that which befell Sauron during the Downfall of Númenor) was indeed devastating for an Ainu, but could not happen unless either the spirit of the Vala or Maia had already been weakened (see below), or Eru directly intervened.
The most powerful rebellious spirits, Melkor and Sauron, did suffer a loss of their being, but only because they allowed part of it to pass into the materials of Arda. This weakening of their original nature allowed them to be injured by others.
Some among the Valar and Maiar did actually incarnate themselves, most notably Morgoth and Gandalf. While in these bodies, they could be forcibly disincarnated or "killed" (though they did not die of old age); but they would suffer no loss of their true being unless previously weakened.
However, upon entering Eä, the Valar and Maiar became bound with it, and thus their fate after its end seems uncertain. This fact brings their ultimate immortality into question.
Elvish "Serial Longevity"
The Elves did not suffer death from old age or disease, as do Men, but they could be slain by injuries and their own grief. Unlike the Valar, experiencing death (which is the separation of their fëa and hröa) violates the Elves' nature, since they were made to live as incarnate beings. The Elves were not free from change and aging, either, but they aged in a different sense than Men: the Elves became ever more weary of the world and burdened by its sorrows, and lived more in the past. In Middle-earth, their bodies would slowly be consumed by their spirits until they were little more than wraiths, in the Unseen. Yet, the Elves could escape this fate by traveling west to Aman.
The Elves are also bound to Eä and cannot escape it as long as it lasts, and can thus be reincarnated after their hröa is destroyed. When their fëa and hröa are seperated, the fëa could travel to the Halls of Mandos. There they can either stay or be reincarnated with a new-born body identical to the previous hröa with the help and approval of Námo. If they were reincarnated they were sent to Aman. There are only two Elves that were sent elsewhere, Glorfindel who was sent back to Middle-earth and Lúthien Tinúviel was also sent back to Middle-earth but as a mortal.
However, this same fact of their nature means that their fate after Eä's end is unknown; it seems that the Elves must die when Eä ends. They must rely on estel to give them hope that this will not be the case. For this reason, the envy often felt by mortals of the Elves' lifespans comes from ignorance of the nature of these lifespans.
Because the Elves can reincarnate, and because their fate after Eä's end is undiscernable, the life of the Elves is "serial longevity", not "immortality".
The race of Men was made mortal, and no Man (save perhaps Tuor) can truly be called immortal in any sense (but see below). However, mortals can have their lifespans extended by the effects of the Rings of Power and other dark arts. The most infamous example is that of the Nazgûl, whose lives were extended by nearly 5,000 years because of their Rings, and the Hobbit Gollum lived 500 years because of his possession of the One Ring. However, because such long life is against the biological and spiritual nature of mortals, it becomes a nearly unendurable torment to them. They also lose their identity and independence; both the Nazgûl and Gollum had become utterly enslaved by the power of the Rings.
However, unlike the Valar and Elves, the ultimate future of Men seems much more assured: it is said that they will participate in the Second Music of the Ainur after the end of days.