The Chiranjivis take birth but do not die. However, at the end of the yuga cycle, the entire universe is destroyed and recreated. That means the Chiranjivis are born again. But what happens to those who were born in the previous cycles? Where do they go?
अश्वत्थामा बलिव्र्यासो हनूमांश्च विभीषण:। कृप: परशुरामश्च सप्तएतै चिरजीविन:॥ सप्तैतान् संस्मरेन्नित्यं मार्कण्डेयमथाष्टमम्। जीवेद्वर्षशतं सोपि सर्वव्याधिविवर्जित॥
The eight Chiranjeevis are: Ashwatthama, King Mahabali, Vedavyasā, Hanuman, Vibhishan, Kripacharya, Parashurama and Markandaya.
At the end of Kali Yuga; Ashwatthama, Kripacharya, Parshurama, and Vedavyasa will be apart of the Saptarishis, during the eighth Manvantarā. There are 14 Manvantaras, in which 14 different Manus rule, and 14 different Indras, and the different families of the devas rule.
As per this excerpt of the Vishnu Mahapurana the next Manu will be Suryasavarni.
In the period in which Sávarńi shall be the Manu, the classes of the gods will be Sutapas, Amitábhas, and Mukhyas; twenty-one of each. The seven Rishis will be Díptimat, Gálava, Ráma, Kripa, Drauńi; my son Vyása will be the sixth, and the seventh will be Rishyasringa.
Please note; Ráma mentioned is Parshurama, and Drauńi mentioned is the son of Dronacharya, i.e Ashwatthama.
Saptarishis reside in Mahar Loka and Jana Loka, and it is implied these four will also reside in either Loka (though Ashwatthama due to his bad deeds, may reside in Mahar Loka, below Jana Loka.)
King Mahabali will also become the next Indra due to a boon granted by Vishnu.
The Indra will be Bali, the sinless son of Virochana, who through the favour of Vishńu is actually sovereign of part of Pátála.
This is also further stated in the Narada Purana.
The eighth Manu will Suryasavarni. The gods will be the sutapas and the Indra will be Vali.
There is no mention in any Puranas where Markandeya or Vibhishan will reside, but due to their great deeds, it is likely they will reside in one of the 7 upper lokas above Bhu Loka (our Solar System.)
Lastly, Hanuman will become the next Sri Brahma. It is stated in Upanishads and in some Puranas that Brahma is a position that changes every Mahakalpa. Each Mahakalpa ends after the end of the 14 Manvantaras. Hanuman will likely have to wait another 2 billion or so years before becoming Brahma before the current Brahma's reign ends.
The current jiva or human that reigns as Brahma, is Shatanand. The Brahma of the first Kalpa was Virinchi. The Brahma of the second Kalpa was Padmabhu, the Brahma of the third Kalpa was Svayambhu, the Brahma of the fourth Kalpa was Parmeshti, the Brahma of the fifth Kalpa was Surajyeshtha, and the Brahma of the sixth Kalpa was Hemagarbha. Only seven Kalpas have passed.
This is described in the Skanda Purana.
Parvati curiously asked Lord Shiva about the reason why Somnath was known by so many different names. Lord Shiva said- ‘ Since the time this divine linga first manifested itself very few blessed souls had the knowledge of it’s existence. Brahma has a life span of one kalpa at the end of which even he renounces his position, giving way to his successor- a new Brahma. In the same manner this divine Linga acquires a new name at the end of each kalpa. The present kalpa is seventh in order as six kalpas have already passed. The name of the present Brahma is Shatanand and this divine Linga is presently famous by the name of Somnath. Similarly it was famous as Mrityunjay during the time of Brahma named Virinchi. During second kalpa this Linga was famous as Kalagnirudra and the name of Brahma was Padmabhu. The third kalpa had Swayambhu as Brahma and the Linga was famous as Amritesh. The name of the fourth Brahma was Parmeshthi in fourth kalpa and the linga was famous as Annamay. In the same way the names of the fifth and sixth Brahma were Surajyeshtha and Hemagarbha respectively and the names of the Linga during their periods were Kritiwas and Bhairav Nath respectively.’
How the Chiranjeevis got to be immortal
Just for the sake of anyone curious, I will say how the Chiranjeevis became immortal.
How Ashwatthama became immortal
Ashwatthama was cursed by Sri Krishna to be immortal after he fired the Brahmastra unto pregnant Uttara.
Always engaged in sinful acts, thou art the slayer of children. For this reason, thou must have to bear the fruit of these thy sins. For 3,000 years thou shalt wander over this earth, without a companion and without being able to talk with anyone. Alone and without anybody by thy side, thou shalt wander through diverse countries, O wretch, thou shalt have no place in the midst of men. The stench of pus and blood shall emanate from thee, and inaccessible forests and dreary moors shall be thy abode! Thou shalt wander over the Earth, O thou of sinful soul, with the weight of all diseases on thee.
How Kripacharya became immortal
Kripacharya was given immortality by Sri Krishna after Kripacharya meditated upon Vishnu.
तावुभौ शन्तनुर्दृष्ट्वा कृपाविष्टः स्वकं गृहम् । निनाय नाम चक्रे च कृपाया विषयौ यतः ॥ ५९ ॥ कृपः कृपीति स कृपस्तपो विष्णोश्चकार ह । तस्य प्रीतस्तदा विष्णुः सर्वलोकेश्वरेश्वरः ॥ ६०॥ प्रादादेष्यत्सप्तर्षित्वमायुः कल्पान्तमेव च। स शन्तनुगृहे तिष्ठन् देवव्रतसखाऽभवत् ॥ ६१ ॥
Kripa meditated on Vishnu, and that lord of lords of the worlds, Vishnu, accorded Kripaacharya with longevity till the end of the era (kalpa), and even with a place in the coming cycle of Seven-sage constellation, Sapta-Rishi mandala.
How Hanuman became immortal
Hanuman became immortal by 3 boons; 1 boon by Brahma, 1 boon by Indra, and 1 boon by Rama.
Then on observing that you are mutilated, highly infuriated is that scent-wafter Air-god and that tempestuous Air-god has not physically circulated throughout the triad of worlds. When the triad of worlds is being roiled with breathlessness, all the administrative gods of universe are bewildered, and they started to supplicate the Air-god for his grace. Oh, chivalric warrior at war, while the Air-god is being supplicated, oh, dear boy, Brahma gave you a boon decreeing your "indestructibility by any missile." On scrutinising that you are unhurt even after hit by Thunderbolt, oh, ablest Hanuma, the Thousand-eyed Indra kind-heartedly gave you a choicest boon saying that your death occurs only by your own volition.
Here is Rama's boon:
[Rama] said to Hanuman: "It is settled that thou shalt live forever, do thou, now observe thy promise. As long as my history shall run current in this world do thou at my command live happily." Being thus addressed by high-souled Raghava Hanuman attained to great delight and said: "As long as the sacred theme shall pass current in this world I shall live here carrying out thy commands."
How King Bali became immortal
King Bali was an Asur king who was very generous, one day, Vishnu in the form of a dwarf, Vamana, had asked King Bali for a piece of land that he could cover 3 steps. King Bali, of course, obliged, and went to do a veneration in honor for the dwarf to gain the land. At this time, Shukracharya tried to stop him, but a straw from the vase pierced his eye, making him blind on his right eye.
Vamana then transformed into a mighty giant, and took over Svarga Loka, Bhu Loka, and Patala Loka. He then granted Bali the boon of Indra during Suryasavarni's reign, the boon of immortality, and being able to live in Sutala Loka.
1: S'rî S'uka said: 'Thus having run into trouble with the Supreme Lord oh King, Bali the Asura king, was despite his awkward position an unperturbed soul who replied positively with the following words.
2: S'rî Bali said: ‘If, oh Lord Praised in the Verses, Your Goodness thinks that what I have promised proved to be false, oh Greatest of the Gods, then let me, in order to be just in this matter and not to have turned to cheating, offer You my head to put the third step of Your lotus feet.’
[3-30 are verses wherein Prahlada Maharaja thanks the Lord for having destroyed the pride of his grandson, and, Vindhyavali, the wife of Bali Maharaja, and Brahma beseech the Lord to not chastise a great soul such as Bali Maharaja.]
31: [The Supreme Lord said:] Through Me he has achieved a position that even for the immortal ones is most difficult to obtain; during the time of Sâvarni Manu he will become the Indra enjoying My full protection.
32: Till then he may go and live in Sutala [the place created by [the heavenly architect] Vis'vakarmâ, where it because of My supervision has been made impossible for the inhabitants to suffer psychically or physically any weariness, exhaustion or defeat.
33: O Indrasena (Bali Mahârâja) please go now, O ruler. May there in Sutala, the place so desirable for even the denizens of heaven, for you surrounded by your people, be all auspiciousness.
34: None of the controllers of the worlds will be able to overrule your command there, not to speak of the common man, for I with my cakra will personally take care of all the Daityas who defy your rule.
How Vedavyasa became immortal
Parashara, the father of Krishna Dwaipayanur Vedavyasa, did austere penance for 100,000 years to Lord Shiva for a son. Lord Shiva granted a son to Parashara, who is Veda Vyasa, and granted the boy the boon of immortality.
It can be found in Mahabharata, Anushashana Parva, Anushashanika Parva, Chapter XVIII.
Parasara said,--'In former times I gratified Sarva, O king. I then cherished the desire of obtaining a son that would be possessed of great ascetic merit, endued with superior energy, and addressed to high Yoga, that would earn world-wide fame, arrange the Vedas, and become the home of prosperity, that would be devoted to the Vedas and the Brahmanas and be distinguished for compassion. Even such a son was desired by me from Maheswara. Knowing that this was the wish of my heart, that foremost of Deities said unto me.--Through the fruition of that object of thine which thou wishest to obtain from me, thou shalt have a son of the name of Krishna. In that creation which shall be known after the name of Savarni-Manu, that son of thine shall be reckoned among the seven Rishis. He shall arrange the Vedas, and be the propagator of Kuru's race. He shall, besides, be the author of the ancient histories and do good to the universe. Endued with severe penances, he shall, again, be the dear friend of Sakra. Freed from diseases of every kind, that son of thine, O Parasara, shall besides, be immortal.
How Vibhishana became immortal
Vibhishana was a righteous king, but he was also born to the Daityas. He had betrayed Ravana, his older brother, and went against him. After Ravana was killed by Rama, Vibhishana became the new king of Ayodha, crowned by Rama Himself.
Brahma granted Vibhishana a boon due to his righteousness. The details of the boon can be found in this section of the Mahabharata.
Saying, 'It shall be so' 'Brahma then addressed Vibhishana, 'O my son, I am much pleased with thee! Ask any boon thou pleasest!' Thereupon, Vibhishana replied, 'Even in great danger, may I never swerve from the path of righteousness, and though ignorant, may I, O adorable Sire, be illumined with the light of divine knowledge!' And Brahma replied, 'O scourge of thy enemies, as thy soul inclines not to unrighteousness although born in the Rakshasa race, I grant thee immortality!'
How Maharishi Markandeya became immortal
Markandeya was a boy, the son of Bhrigu, who was destined to die at 16 years old. According to the Skanda Mahapurana, the Saptarishis bring Markandeya to Brahma, which Brahma then says that Markandeya will live as long as He will.
Thereafter Brahmā was paid obeisance by that boy. In the presence of the sages, the boy was blessed, “Long live” by Brahmā.
On hearing the words from Pitāmaha, those sages were pleased. On seeing the sages who appeared surprised Pitāmaha spoke to them, “For what specific purpose did you come here? Why was the boy introduced?”
The sages said: 30. Mṛkaṇḍa is the son of Bhṛgu. The life span of his son is of short duration. Realizing this, the father tied the Mekhalā (religious girdle for sacred thread ceremony) before due time.
31-33. The sacred thread was also put. The boy was instructed by the Brāhmaṇas: “Whoever may be the twice-born that you may meet walking about in the world, O dear son, you must pay obeisance to him always. Then, O excellent one, we were met by the boy as we were engaged in pilgrimage. As Providence willed it, O Pitāmaha, he was given the blessing:” Be a long-lived one” by us, as we were bowed to.
- He was brought to your presence and the same thing was uttered by you. O Lord, how can our words as well as those of yours turn out to be untrue?
35-36a. Pointing out the boy the Lotus-born One laughed and said: “This boy Mārkaṇḍeya shall have a life span on a par with that of mine. At the beginning and the conclusion of the Kalpa he will assist me.”
How Parshurama became immortal
I was unable to find any credible verses that state how Parshurama became immortal.
I hope this helped!