The first mishna in Parah talks about the age that a cow can be and still be valid as a parah adumah:
רבי אליעזר אומר עגלה בת שנתה ופרה בת שתים וחכ"א עגלה בת שתים ופרה בת שלש או בת ארבע ר"מ אומר אף בת חמש כשרה הזקנה אלא שאין ממתינין לה שמא תשחיר שלא תפסל
R' Eliezer says a calf is in its first year, a cow is in its second year. The Chachamim say a calf is in its second year, a cow is in its third year. R' Meir says even an old cow in its 5th year is ok, but we don't wait because it might grow black hairs.
The first parah adumah was done on the second of Nissan (Rashi in several places but I can't find them now). This means that the cow was born in Egypt. According to R' Eliezer, it could have been born as late as Rosh Chodesh Nissan of החדש הזה לכם (which is a nice connection to reading Parah the week before Hachodesh). According to the Chachamim and R' Meir, it was born before the plagues even started! Either way, how did its owner know to treat it specially and not accidentally disqualify it by putting something on it?
Several suggestions:
A younger cow can be used bedieved? The Rash and Tosfot Yom Tov on that mishna suggest that an older cow is ok bedieved even according to R' Eliezer, so maybe a younger one is too. But I haven't found anyone who says so explicitly, and the Rambam at the beginning of Hilchot Parah strongly implies that it's not.
The owner had no idea, but Hashem made a miracle that nobody ever ended up putting any burdens on it? It's possible, but then how did the owner remember that he hadn't done it without thinking, since he would have had no reason to think about it?
It was a wild cow that Hashem caused to wander into the camp? Again this raises the same question - how did anyone know that it had never had a burden on it?
Hashem told the owner of the cow to be careful with it through a private, unrecorded nevuah? (According to the Chachamim/R' Meir it would have to be through Miriam or Aharon or someone else, since Moshe was still in Midyan.) This would need a very strong source.