What does deathless mean?
The Deathless is a synonym for Nibbana. The Deathless state is the state where one is freed from birth and thereby death. Conditioned phenomena constantly arise and fall. In other words: They must die. Nibbana is unconditioned, unborn, it does not arise and fall and therefore must not die.
Here are some quotes from the Majjhima Nikaya and Samyutta Nikaya where the Buddha talks about The Deathless state in relation to Nibbana. There are also some notes from the author (Ven. Bhikkhu Bodhi):
"He turns his mind away from those states and directs it towards the deathless element thus: "This is the peaceful, this is the sublime, that is, the stilling of all formations, the relinquishing of all attachments, the destruction of craving, dispassion, cessation, Nibbana"
-- MN 64: Mahamalunkyaputta Sutta, p. 540, Bodhi translation
"Then at that point the Blessed One uttered this exclamation:
The greatest of all gains is health,
Nibbana is the greatest bliss,
The eightfold path is the best of paths
For it leads safely to the Deathless."
-- MN 75: Magandiya Sutta, p. 613, Bodhi translation
"The eleven "doors to the Deathless" are the four jhanas, the four brahmaviharas, and the first three immaterial attainments used as bases for the development of insight and attainment of arahantship."
-- Notes to sutta 52, p. 1252
MA: He "turns his mind away" from the five aggregates included within the jhana, which he has seen to be stamped with the three characteristics. The "deathless element" (amata-dhatu) is Nibbana.
-- Notes to sutta 64, p. 1266
"MA says that the arahantship of the dry-insight meditator is intended. MT adds that arahantship is called "the Deathless" because it has the flavour of the Deathless, being attained on the basis of Nibbana the Deathless."
-- Notes to sutta 106, p. 1312
Here is a quote from the Samyutta Nikaya:
"This is what the Blessed One said. Having said this, the Fortunate One, the Teacher, further said this:
"One who desires merit, established in the wholesome, Develops the path to attain the Deathless;
He who has reached the Dhamma's core,
Delighting in destruction,
Does not tremble thinking,
'The King of Death will come."
-- SN 55: Sotapattisamyutta, p. 1829, Bodhi translation
"Bhikkhus, I will teach you the taintless and the path leading to the taintless. Listen to that ...
"Bhikkhus, I will teach you the truth and the path leading to the truth ... I will teach you the far shore ... the subtle ... the very difficult to see ... the unaging ... the stable ... the undis integrating ... the unmanifest ... the unproliferated ... the peaceful ... the deathless ... the sublime ... the auspicious ... the secure ... the destruction of craving ... the wonderful ... the amazing ... the unailing ... the unailing state ... Nibbana ... the unafflicted ... dispassion ... purity ... freedom ... the unadhesive ... the island .., the shelter ... the asylum ... the
-- SN 43: Asankhatasamyutta, p. 1378, Bodhi translation
"The removal of lust, etc., is a designation for the unconditioned, deathless Nibbana element. The destruction of the taints is arahantship. The removal of lust, etc., is a name for arahantship too."
-- Notes to sutta 45, p. 1893
The Dhamma Wiki has a list of "33 Synonyms for Nibbana".