Unless you learned the 4th perek of Rosh haShana, the whole idea of having 2 days of rosh chodesh should strike you are strange / impossible. On day 30 of month X, if 2 witnesses come and say they saw the new moon, then beis din would declare it rosh chodesh and start the new month. If 2 witnesses did not show up, then it would be just another, ordinary weekday and the next day would be rosh chodesh. How do we get 2 days of rosh chodesh?
The Mishna in R"H tells us that for hundreds of years witnesses always came early in the day on day 30 of Elul. One time during bayis sheni they showed up late in the day and it caused all kinds of confusion in the mikdash. The kohanim on that day operated under the assumption that since it was late in the day and no witnesses had come, it would be an ordinary weekday, i.e. no korban musaf, regular shirah during nisuch ha'yayin, etc. When the witnesses did eventually come, it meant the day was in fact rosh chodesh/rosh hashana and a korban musaf was required, the shirah was different, etc. (let's leave the technical details aside). In response to this turn of events R' Yochanan ben Zakai made a takanah: if witnesses show up late, they will automatically be held over until the next day. However, instead of declaring day 30 as not rosh chodesh/rosh hashana, both day 30 and the next day would be celebrated. In other words, day 30 would always be rosh chodesh -- witnesses coming late or coming the next day could only add an extra day, not subtract or change the status of day 30. That, in an oversimplified nutshell, is how we get 2 days.
Based on this account, historically there should never have been a 2 day rosh chodesh or rosh hashana until sometime during the second temple period.
Yet I am sure you were listening to yesterday's haftarah, the haftarah of machar chodesh, where we read how on the second day of rosh chodesh Shaul took note of David's second day of absence from the royal table and put Yehonasan on the spot and asked him to explain where David was.
2 days of rosh chodesh in the days of Shaul, long before R' Yochanan ben Zakai? How did that happen?
See the note of the Tziyun Yerushalayim on the bottom of Yerushalmi Ta'anis 22a in the Vilna edition.
II. While on the topic of that haftarah, at the end of the story we are told that Yehonasan and David wept "ad higdil David" and Yehonasan then departed. Most of the meforshim I saw understand this line to mean that David's crying became so great and loud that Yehonasan felt he had to leave lest David be discovered. My wife suggested that perhaps the opposite was true -- the sign of a gadol is self control, much like Aharon in our parsha, "vayidom Aharon," restrained his crying. Perhaps it is Yehonasan who continued to cry while David controlled his emotions, and therefore, it is Yehonasan who felt he had to depart.