Bamidbar (Num.) 9:1, which begins the section related to Pesach Sheni says that the event occurred in the second year from leaving Egypt. Beginning in verse 9, we learn about the laws of Pesach Sheni.
As Pesach Sheni applies to those who are tamei, does this mean that during the 1st year no one was tamei, so there was no need for Pesach Sheni, then?
The laws of tum'ah were not given until the Torah was given on Shavuos (or possibly later, depending on whether all mitzvos were given on Shavuos). Thus, even people who touched a corpse would not have been tamei and were able to bring the Korban Pesach at the correct time.
Note that in the verses about the laws of the first Korban Pesach, there is no mention that a tamei person can not bring it.
The Pesach in Egypt was the Pesach of the first year. Since the year was being counted with Nisan as month 1, then month 1 of year 2 was the first Pesach that was being held in the desert. That is, "in the second year" is the quote.
The Lord spoke to Moses in the Sinai Desert, in the second year of their exodus from the land of Egypt, in the first month, saying:
א. וַיְדַבֵּר יְהֹוָה אֶל משֶׁה בְמִדְבַּר סִינַי בַּשָּׁנָה הַשֵּׁנִית לְצֵאתָם מֵאֶרֶץ מִצְרַיִם בַּחֹדֶשׁ הָרִאשׁוֹן לֵאמֹר:
The children of Israel shall make the Passover sacrifice in its appointed time.
ב. וְיַעֲשׂוּ בְנֵי יִשְׂרָאֵל אֶת הַפָּסַח בְּמוֹעֲדוֹ:
A year after the Exodus, G‑d instructed the people of Israel to bring the Passover offering on the afternoon of the fourteenth of Nissan, and to eat it that evening, roasted over the fire, together with matzah and bitter herbs, as they had done the previous year just before they left Egypt.
Since the mishkan had just been set up (Shmini had just occured on rosh chodesh Nisan), Aharon had to set up the Para Aduma first. Thus, people who were tamei mais would not have had the chance to complete becoming tahor. Since Aharon had not yet been installed as kohen gadol until then, he could not have prepared the parah adumah earlier, even if the commandments of parah adumah had been given as early as Mara (or at least at Har Sinai).
The meforshim say that they were people who had completed the course of becoming tahor, and were just waiting until the sun set. The question involved if they could join a chaburah that had fully tahor people in it. The tahor people would bring the korbon and they (having become fully tahor after the sun set) would join the (pre-arranged) group after sun set to eat.
The ruling was that they could not do this and had to wait for Pesach Sheni. It all depended on their status as of the time of the shechitah.
This is also why some say that the people were those who carried out Nadav and Avihu. They had become Tamei on Rosh Chodesh Nisan, and would have required 7 days to become tahor. However, they had to wait until the parah adumah became available for the sprinkling.
As far as everyone bringing the korban Pesach in the first year, the meforshim said that no one died from the makos (aside from those buried during the plague of darkness). As a result, even had the laws of tumah been established (which they had not been), everyone would have become tahor already (since the parah adumah had not yet been commanded). Since the blood of the korbon Pesach was what saved the Bnei Yisrael from the final plague, everyone had to be eligible.
Either the laws of tum'as meis did not yet apply or they had some method from the avos for becoming tahor. The torah does not specify since we do not need to know the details.
