The date of Rosh Chodesh was determined by testimony. However, it was also calculated. Since the calculations weren't binding in and of themselves, the testimony was made to align with the calculations by various methods.
The new month was pre-calculated in that it couldn't be more than 30 days, and on the 31st day the previous month automatically became a 30-day month and the next month began. However, they wouldn't start a new month on the 30th day (thus making the previous month 29 days) without witnesses; if only the court saw it, they would bring people to testify for them.
According to the Mishna (Rosh Hashana 3:1, translating the most relevant parts):
ראוהו בית דין וכל ישראל--נחקרו העדים, לא הספיקו לומר מקודש, עד שחשיכה--הרי זה מעובר. ראוהו בית דין בלבד--יעמדו שניים ויעידו בפניהם, ויאמרו מקודש מקודש. ראוהו שלושה, והם בית דין--יעמדו שניים, ויושיבו מחבריהם אצל היחיד ויעידו בפניהם, ויאמרו מקודש מקודש: שאין היחיד נאמן על ידי עצמו
If the court and all of Israel saw it (the new moon), the witnesses were checked, but they didn't manage to say "sanctified" (making the previous month 29 days), it is a leap month.
If only the court saw it, two should stand and testify before them, and they they say "sanctified, sanctified."
Whether they actually verbally sanctified the new month if it was 29 days long or 30 days long is a matter of dispute (Mishna Rosh Hashana 2:8 and BT 24a). The anonymous Mishna says they would sanctify it whether or not they saw the moon on the 30th or 31st day; Rabbi Eliezer son of Rabbi Tsadok says that it was automatically sanctified if it appeared on the 31st day, and there was no need to sanctify it; Plimo says they would only sanctify it if it appeared on the 31st day; and Rabbi Eliezer the son of Rabbi Shim'on says they wouldn't sanctify it at all.
Rabban Gamliel had a tradition regarding the length of the month (BT 25a) and seems to have accepted witnesses whose testimony conformed to his calculations, even when their testimony was somewhat unreliable (Mishna 2:8). Similar to the case mentioned above where the court brings two people to testify for them. According to Rabbi Yehoshua son of Levi (20a), they would intimidate (מאיימין) the witnesses into extending the month (saying they didn't see the moon), but not into shortening it (saying they did see the month); Rabbi Yochanan used to teach also that they would intimidate them into shortening it.
Second Temple Period
As for the question of how much of this process was observed during the Second Temple period, I haven't really found a detailed source. The Mishna (2:5) mentions with regard to the place (בית יעזק) to which the witnesses came to testify:
בראשונה, לא היו זזים משם כל היום; התקין רבן גמליאל הזקן, שיהו מהלכין אלפיים אמה לכל רוח
Since this source quotes the elder Rabban Gamliel who lived in that period, I think it's clear that they accepted witnesses, but the source doesn't speak about calculations. However, the statement of Rabban Gamliel (the younger) in BT 25a that he had a family tradition regarding calculations (כך מקובלני מבית אבי אבא) may date to his ancestors from the Temple period.
The Tosefta (2:7) says:
אמר ר' יהושע בן קרחה דברים אלו התקינן רבן יוחנן בן זכאי משחרב בית המקדש לכשיבנה הבית במהרה יחזרו דברים אלו ליושנם
Rabbi Yehoshua the son of Korcha says: Rabban Yochanan ben Zakkai enacted these things after the Temple was destroyed. When it will be built soon, things will return to the way they were.
Given that this is said in the context of Rosh Chodesh (cf. Mishna 4:4), it might be that at least some of the practices relating to the New Moon started after the destruction of the Temple. It's not clear to me from this source exactly which.