This is not exactly about PST, but I think I can find the best answers here:

In fantasy games (like DnD, but not only there) you meet lots of creatures who are called immortal.
I am not an DnD expert, but think about gods, demons and devils, angels, elementals?, undead? others???
But there are stories that such creatures have been killed and in many games your char is the killer.

-Does immortal mean, that a creature does not die just because time passes, but it can be killed by performing actions that would kill a "normal lifeform"? (like cutting off the head (if it has one head) or burning it to ashes (does not work for fire elementals))

- Are there several "degrees of immortality"?
Most undead continue to exist for a very long time, but if you kill them they stay dead. (Some people made themselves undead to cheat death like liches or Bodhi from BG2). Things may look different when you look at gods or demons or some other things.

- What happens to a god/demon/devil/angel/something else when you kill it?
In PST (and other games) you fight a lot of such creatures. In BG2 ToB you have the option to beat a demon lord in in PST you have to fight an angel. When you succeed, you get exp for killing it and you see a dead body on the ground. But the game tells you they are not really dead.

- It looks like demons, angels and gods reproduce themthelves like normal lifeforms. The fact that they have children with mortals (tieflings, aasimar) supports that. In many games it looks also like there are some creatures of the same type who look older than others. If those creatures have children but they cannot die, the multiverse must be crowded with them until all existing space is filled with their bodies.

- Regarding the point above: Grace says she has lots of sisters and her parents sold her to the devils. Trias (and a celestrial party member from NWN2 MotB) have problems with their father. This means those creatures are born as small children, they grow until they are adults and then they stay this way and simply grow more powerful over time? So a demon lord is just a demon who survived long enough to become so powerful that most other demons connot harm him anymore?

- Does it matter on which plane you "kill" such a creature?

- Did the one who invented those games actually think about those questions?
Or was it like this:
player: Why is char A in game X and also in game Y that is set 1000 years later?
dev: She is immortal.
player: I have the greatsword of demon slaying. What happens if I attack her?
dev: You get many exp and an artifact.
player: If I can kill her, why is she immortal?
dev: shut up and buy more games!

It is depends on the setting.
Example: Tolkien take the high elves as immortals and even the high spirits, yet the first were mortals (and for when Sauron reach his peak, they were a minimum). Liches and vampires can be eternal too, the terrasque also. Again, depends, on D&D frankly is almost impossible to finished a deity, as long someone remember him, there will be a shadow, reflection or anything related to the dead deity.

The outsiders usually return to their plane, but I think only devils and demons preserve their form and memories (D&D here). Plus prayers. (Again, depends on the setting) NWN2 with the mask of betrayer.
A little with Cyrc and Bhaal in the BG's serie (but this only in the Throne of Bhaal)
Plus P&P campaigns

The Planescape setting this game was based on answered exactly these sort of questions, and much of it became incorporated into standard D&D rules. Generally yes. Most types of immortals have some kind of weakness that a well equipped mortal could exploit to kill them. Those of opposing alignments (e.g. angels and demons) are often adept at killing each other as well. Immortal implies a living creature. Undead don't get to enjoy most of the benefits of living, except perhaps for vampires. Becoming a lich is a rather desperate act and carries heavy costs. Demons, devils, angels, and such return to their plane normally. They're not really supposed to leave a corpse, because they don't have the body/soul separation of mortals. Killing a god is almost impossible under normal circumstances. Within their own realms they're basically untouchable, and with all their servants (mortal and otherwise) they have little reason to leave. A dead god is said to leave a massive "corpse" on the astral plane, which Githyanki sometimes build their cities upon.

Immortals are "born" out of the essence of their own plane. Some of them have features in common with mortals. Apparently enough to breed with them in some cases. The origins of gods vary. Some are said to be primordial, some were created by other gods, and a few ascended from mortals. More or less, but they don't grow from children. Beings that have a mortal and immortal parent may do so. Varies depending on the creature. Typically killing them sends them back home. Killing them on their home plane may destroy them. Well if you give a creature stats, someone will certainly attempt to kill it, just to see what happens. The makers of Planescape must have been aware of this, because they never gave stats for the Lady of Pain, and nobody messes with her.

Thank you for your answers.

some more things:

- Does it mean Fall from Grace, Trias and some others do not tell the truth when they talk about their families?
You just said that immortal creatures are not born like normal animals.
But those chars (and others, including when talking about gods) talk about their family like normal people do.
I am almost certain that Grace tells me that she has many sisters and her parents sold her. If I want to convince Trias to seek redemption I have to say something like "remember your fathers eyes" (I am not 100% sure)

- Regarding the degrees of immortality, TNO seems to have a higher degree than others. He gets up again when he is killed normally, but some powerful creatures and the destruction of his body will kill him permanently.

- So you say that only living things can be called immortal (makes sense to me). So undead and constructs are not immortal, even if they are sentient and they can exist for a very long time. There are some creatures where I am not sure if they count as "living" or not. For example, are elementals alive?
By the way: I play Vampires the Masquerade Bloodlines now (not DnD, I know), and the undead there have an almost normal "life". As long as they avoid sunlight and drink some blood sometimes (out of a glass, if they are civilized ;-)) they seem very normal.

- The planes seem to be very complicated. I have no problem with the concept of a multiverse, but this outsider thing is strange. So a human from the material plane just dies, but when a human from Sigil dies in another plane he returns to Sigil? The strangest thing in this multiverse is, that almost all planes allow the existence of humanoid life. Most likely this is because those games were made by human and they assume that players chose a human like character.
In our real world I cannot exclude the existence of other universes, but I assume they would have completely different laws of physics, so time, space and matter as we know it does not exist at all. This would also exclude the existence of life as we know it.
Considering the fact that DnD is full of half-creatures (meaning both parents have a different species, like half demons), some scientists have said that it is more likely that a human has a child with a flower from earth than with a creature from another planet (or even another universe).

- One more thought. When the game ends, TNO is doomed to fight in the blood war for eternity. So permanent death (being killed by the lady, using a special blade when facing the transcendent one) does not seem so bad at all.

IIRC, after death non-planars are going to be reborn as petitioner on the appropriate Outer Plane, which in turn might grow up to the full-right planar somewhen. If the planar dies on the home plane, (s}he simply reborns. If (s)he's unfortunate to do it on the other plane, there goes the true death. Don't know if "planar" might be apllied for children of cluelesses being born in Sigil (for example).
Please, somebody, correct me if I'm wrong. Again, IIRC, the Outer Planes are materialised beliefs, religions, ideals, and so on, so there's technically should be no problems for humanoids, and that's why there'e so many of them there.
On the other hand, the Inner Planes are pure elementa and quasi-elementa. I don't think one would find Fire Plane very hospitable. Eternity might have its end as well.

Succubi could very well be an exception, given their nature. To have "forgotten the face of your father" means you have disgraced yourself. Trias is an angel and doesn't have a father, but he almost certainly has friends and superiors who would be disappointed in him.

The Nameless One's immortality is a completely unique case detailed throughout the game.

Elementals are the inner planes equivalent to outsiders, being made of the raw essence of their planes. They are alive and sapient, but not very social. Vampires, D&D or not, have always blurred the lines between living and undead. However, even in Bloodlines there is the scientist who notes that all of your biological functions have ceased.

Dead humans go to whatever plane best matches their faith/alignment, unless some other force intervenes. Devils, for example, will sometimes tempt newly dead souls to join them in order to avoid a "worse" fate under the heel of some evil deity, and demons are known to steal souls outright for whatever perverse use they have in mind.

Planes can have completely different physical laws, and sometimes those laws change at the whim of a local god. Of course, given how everything in this setting is so infused with magic, the tenets of known physics and biology don't really apply.