History of the Siddur

The Beginning: Shema, the Amida, and the Priestly Blessings

(א) מאימתי קורין את שמע בערבית. משעה שהכהנים נכנסים לאכול בתרומתן, עד סוף האשמורה הראשונה, דברי רבי אליעזר. וחכמים אומרים, עד חצות. רבן גמליאל אומר, עד שיעלה עמוד השחר.

Mishnah Berakhot 1:1

(1) From when may one recite Shema in the evening? From the time when the Kohanim go in to eat their Terumah [produce consecrated for priestly consumption], until the end of the first watch – so says Rabbi Eliezer. And the Sages say: Until midnight. Rabban Gamliel says: Until the break of dawn.

This is the first Mishna of the First tractate of the Mishnayot that was completed by Rebbi Judah the Prince before his death in 217 CE. It was the first book of laws of the "Oral Torah" that was set down in writing in the Jewish canon. It is the source of most of the Jewish traditions and rituals we do today in he synagogue and the home.
Notice that the opening word is "From When," indicating that this has been an established, axiomatic custom of the Jewish people from much before then, and the Mishna was just coming to tell you the "when" and the "how."

משנה סוטה ז׳:א׳

(א) אלו נאמרין בכל לשון, פרשת סוטה, ודוי מעשר, קריאת שמע, ותפלה , וברכת המזון, ושבועת העדות, ושבועת הפקדון.

Mishnah Sotah 7:1

(1) The following are said in any language: the paragraph of Sotah (Numbers 5:19-22), declaration of tithes (Deuteronomy 26:13), the recitation of Shema (Deuteronomy 6:4-9), prayer, the blessing after a meal, the oath of testimony, and the oath of a deposit.

Another example of a law regarding Shema from the Mishna regarding the language you can recite it in (it can be said in any language, even according to the Law, indicating how Judaism was a religion for Jews living in the diaspora and even was an allowance within Israel, as many Jews spoke Greek and Aramaic at that time). So the Shema was obviously very established at that time, and this is almost 2000 years ago (maybe even going back another 400-600 years to the times of Ezra) .

Ezra arrives on the scene...

סוכה כ׳ א:מ״ז

שבתחלה כשנשתכחה תורה מישראל עלה עזרא מבבל ויסדה חזרה ונשתכחה עלה הלל הבבלי ויסדה חזרה ונשתכחה עלו רבי חייא ובניו ויסדוה

Sukkah 20a:11

For in ancient times when the Torah was forgotten from Israel, Ezra came up from Babylon and established it. [Some of] it was again forgotten and Hillel the Babylonian came up and established it. Yet again was [some of] it forgotten, and R. Hiyya and his sons came up and established it

The Amidah/Shmoneh Esreh prayer is attributed to the Great Assembly at the time of Ezra (480-440 BCE). He was very instrumental to the way Judaism is practiced today, including (according to the Talmud) the reading of the Torah in public and many other items. Some historians also say that he was the first person to create a Sefer Torah in the way we know it today.

מגילה ל״א ב:מ״ז

עזרא תיקן להן לישראל שיהו קורין קללות שבתורת כהנים קודם עצרת ושבמשנה תורה קודם ר"ה

Megillah 31b:10

Ezra established for Israel that they should read the curses in Leviticus before Shavuot and those in Deuteronomy before Rosh Hashanah. ...

ברכות ל״ג א:ע״ט

מכדי אנשי כנסת הגדולה תקנו להם לישראל ברכות ותפלות קדושות והבדלות

Berakhot 33a:25

"It is a fact that the men of the Great Assembly instituted for Israel benedictions and prayers, Sanctifications and Divisions ;

משנה אבות ב׳:י״ג

(יג) רַבִּי שִׁמְעוֹן אוֹמֵר, הֱוֵי זָהִיר בִּקְרִיאַת שְׁמַע (וּבִתְפִלָּה). וּכְשֶׁאַתָּה מִתְפַּלֵּל, אַל תַּעַשׂ תְּפִלָּתְךָ קֶבַע, אֶלָּא רַחֲמִים וְתַחֲנוּנִים לִפְנֵי הַמָּקוֹם בָּרוּךְ הוּא, שֶׁנֶּאֱמַר (יואל ב, יג) כִּי חַנּוּן וְרַחוּם הוּא אֶרֶךְ אַפַּיִם וְרַב חֶסֶד וְנִחָם עַל הָרָעָה. וְאַל תְּהִי רָשָׁע בִּפְנֵי עַצְמָךְ:

Pirkei Avot 2:13

(13) Rabbi Shimon says: Be careful in the reciting of Shema (and praying). When you pray, do not make your prayer fixed, rather prayers for mercy and supplication before the Omnipresent, blessed be He, as it says (Joel 2, 13), "For He is gracious and merciful, long-suffering and full of kindness, and repents of the evil." And do not be wicked in your own eyes.

Here we see how a Rabbi in the Mishnah talks about being careful about reciting the Shema and the Amidah ("Tefilah" in the Mishnah and Talmud in the context of the law refers usually to the Amidah.

משנה ברכות ד׳:ג׳

(ג) רבן גמליאל אומר בכל יום מתפלל אדם שמונה עשרה. רבי יהושע אומר מעין שמונה עשרה. רבי עקיבא אומר אם שגורה תפלתו בפיו יתפלל שמונה עשרה. ואם לאו מעין שמונה עשרה.

Mishnah Berakhot 4:3

(3) Rabban Gamliel says: Every day a person must pray eighteen [blessings of Shemoneh Esrei]. Rabbi Yehoshua says: [One may say] an abbreviated [form of the] eighteen [blessings]. Rabbi Akiva says: If his prayer is fluent in his mouth, he must say eighteen; and if it is not -- an abbreviated eighteen.

ברכות כ״ח ב:י״ב-כ״ג

מתני׳ רבן גמליאל אומר בכל יום ויום מתפלל אדם שמנה עשרה רבי יהושע אומר מעין י"ח ר"ע אומר אם שגורה תפלתו בפיו מתפלל י"ח ואם לאו מעין י"ח. גמ' ת"ר שמעון הפקולי הסדיר י"ח ברכות לפני רבן גמליאל על הסדר ביבנה אמר להם ר"ג לחכמים כלום יש אדם שיודע לתקן ברכת הצדוקים עמד שמואל הקטן ותקנה.

Berakhot 28b:12-23

MISHNAH Rabban Gamaliel says: Every day one should pray the eighteen [benedictions]. R. Joshua says : The abstract of the eighteen [benedictions]. R. 'Akiba says: If his prayer is fluent in his mouth, he should pray the eighteen ; GM' Our Rabbis have taught : Simeon the Cotton-dealer arranged the eighteen benedictions in order in the presence of Rabban Gamaliel at Jabneh. Rabban Gamaliel asked the Sages, "Is there anyone who knows how to word the benediction relating to the Minim?" Samuel the Small stood up and worded it.

שבת קי״ח ב:ה׳

מאוכלי שלש סעודות בשבת א"ר יוסי יהא חלקי מגומרי הלל בכל יום איני והאמר מר הקורא הלל בכל יום הרי זה מחרף ומגדף כי קאמרינן בפסוקי דזמרא

Shabbat 118b:5

...

From the time of Rabban Gamliel II (80 CE, 10 years after the destruction of the Second Temple) till Rav Amram Gaon (D.875), there wasn't necessarily a specific prayer book, but it was a bit arbitrary depending on each synagogue and the style of the community, as long as the Shema, the Amidah, and the Priestly blessings were said. It wasn't until the latter scholar created the first official "siddur" in the way we know it today. It is to be noted that since there were no printing presses in those days and we don't have an original copy, there are discrepancies in the text and things could have been added later. But he was the first one to create a full-fledged siddur and was the basis for those that came after him, including Sadiah Gaon (882/92-942) and Maimonides (1135/38-1204).
After them, there were other scholars who added, edited, and tweaked along the years.
Bare in mind that since there were no printing presses, this all was not fully set until the press became available and mass production began to happen.
The earliest one is from 1486 that was printed by the famous Soncino family, but a siddur was not mass produced the was known it today till the mid 19th century.
Still, there were many versions of the siddur without any central control, and only within the last 250-300 years has it been more organized and has come down to 3 main versions (Nuschaot).
1) Ashkenazi
1a) Italian Nusach, which is based on the Ashkenazi version, but has its unique additions.
2) Sfaradi
2a) Nusach Ari, which most Hassidim use, it is based on the Sfardi Nussach with an emphasis on Kabalistic elements
2b Spanish and Portuguese (no Kabalistic elements)
3) Yemenite