Gemara

R. Alexandri: One who prays must take three steps back (afterwards). After this, he gives Shalom.

Rav Mordechai: After taking three steps, he must stand there (for some time);

This is like a Talmid taking leave of his Rebbi. If he turns around immediately, this is like a dog eating its vomit.

Support (Beraisa): One who prays must take three steps backwards (afterwards). If he does not do so, it would have been better had he not prayed.

Shemayah says, first he gives Shalom to the right, then he gives Shalom to the left. We learn from "Mi'Mino Esh Das Lamo" and "Yipol mi'Tzidcha Elef u'Rvavah mi'Minecha".

Rava saw Abaye he gives Shalom to his right before to his left.

Rava: One does not gives Shalom to his right first. Rather, he gives Shalom to his left, which is Hash-m's right (one is considered to be facing Hash-m during Tefilah).

R. Chiya brei d'Rav Huna: I saw Abaye and Rava take three steps back in one Keri'ah (bowing).

Rishonim

The Rif (Berachos Sof 24a) and Rosh (Berachos 5:23) cite our Gemara, with the following addition to Rav Mordechai (who forbids returning immediately after taking three steps back):

Rather, he must stand there until the Shali'ach Tzibur begins (the repetition), the he returns to his place.

Some say that he does not return until the Shali'ach Tzibur reaches Kedushah.

Question (Teshuvas Rashba 436): This is not in the Gemara! Rav Mordechai is a Ga'on, not an Amora! He compares one who returns immediately to a dog eating its vomit, like we say about one who confesses sins from which he repented and confessed previously and did not repeat them (according to the opinion that forbids confessing again), for it looks like he returns to confess again.

Answer (Bach on Rif): Rav Mordechai is an Amora. His teaching is in Yoma 53b.

Note: Our Gemara does not give the Shi'ur how long to wait. Dikdukei Sofrim says that Rav Mordechai's teaching is not in the Kisvei Yad of the Gemara.

R. Yonah (DH Ela): If one wants he may return once the Shali'ach Tzibur reaches Kedushah.

Divrei Chamudos (66): The Terumas ha'Deshen (13) does not require the Shali'ach Tzibur to take three steps back after his repetition. Rather, he waits until (Oseh Shalom at the end of) Kaddish Shalem, which was enacted after every Tefilah (and then steps back). Even if there are interruptions in the middle, e.g. Kedushah (in 'U'Va l'Tziyon'), Kri'as ha'Torah, Hallel or Avinu Malkeinu, these are all considered parts of Tefilah. This reason applies even if the Shali'ach Tzibur did not pray silently beforehand. However, the Rema and Avudaraham exempt him only if he prayed silently (and stepped back) beforehand. Then we do not require another three steps after the repetition, to avoid making the Tzibur wait.

Rambam (Hilchos Tefilah 5:10): When one finishes Tefilah he bows and takes three steps back. While bowing he gives Shalom to his left, then to his right, then he lifts his head.

Piskei Rid (DH Amar): Abaye and Rava took three steps back in one Keri'ah, i.e. one step the size of three steps.

Poskim

Shulchan Aruch (OC 123:1): (After Tefilah) one takes three steps back in one bowing.

Source (Beis Yosef DH Chosav Od): We take three steps corresponding to three Mil that Benei Yisrael distanced themselves from Har Sinai (out of fear of the Shechinah) at the time of Matan Torah. Also, Moshe entered darkness, cloud and Arafel (thick cloud) to speak to Hash-m, and similarly left these three afterwards (Medrash). Shibolei ha'Leket cites Ge'onim who say that since when a person prays he is in a Kodesh place, afterwards he must return to Chol. Rav Hai Gaon says that it is because Tefilos correspond to Korbanos, and there were three stratums of rock between the ramp and the Mizbe'ach. A Kohen descending from the Mizbe'ach would traverse them walking backwards. R. Mano'ach says that we learn from "V'Ragleihem Regel Yesharah" (the plural teaches two, and the singular another one). The Avudaraham says that we learn another three from (the continuation of the verse) "V'Chaf Ragleihem k'Chaf Regel Egel". One must walk another three steps to return to his place, making six in all.

Source (Magen Avraham 1): Some say that it is because Nebuchadnetzar merited to destroy the Beis ha'Mikdash in the merit of three steps taken to honor Hash-m (Shir ha'Shirim Rabah 3:6. According to Sanhedrin 96a, he took four steps.) This is why afterwards we pray for the Mikdash to be rebuilt.

Magen Avraham (6): According to the Avudaraham, who says that one takes another three steps to return to his place, no one should walk in front of him before he returns, for this interrupts the six steps.

Mishnah Berurah (1): One should bow enough so that all of the vertebrae stick out.

Shulchan Aruch (ibid.): Before straightening up, while saying Oseh Shalom bi'Mromav he turns to his left; while saying Hu Ya'aseh Shalom Aleinu he turns to his right; afterwards he bows in front, like a Talmid taking leave of his Rebbi.

Source (Mordechai Berachos 111 citing Avi ha'Ezri): While saying Oseh Shalom he turns to his left; while saying Ya'aseh Shalom Aleinu he turns to his right; he concludes Al Kol Yisrael. The custom is to bow in front like a Talmid taking leave of his Rebbi.

Mishnah Berurah (3): The same applies to the three steps at the end of Kaddish.

Shulchan Aruch (ibid. 2): After taking three steps back he stands there and does not return to his place until the Shali'ach Tzibur reaches Kedushah, or at least until the Shali'ach Tzibur begins the repetition.

Beis Yosef (DH uv'Makom): One who returns immediately shows that he did not step back like one who takes leave of his Rebbi.

Taz (3): One who returns immediately shows that he is unhappy with his Tefilah and wants to pray again. The Gemara likens him to a dog eating its vomit because he disgraces his Tefilah. If he waits until the Shali'ach Tzibur begins, it is clear that he returns in order to listen attentively.

Mishnah Berurah (9): If one steps back just when the Tzibur reaches Kedushah, he may step forward again immediately.

Mishnah Berurah (10): L'Chatchilah, one should not return until the Shali'ach Tzibur reaches Kedushah. If he is cramped or there are Piyutim before Kedushah he may return once the Shali'ach Tzibur begins the repetition.

Rema: The Shali'ach Tzibur remains in his place for the time needed to walk four Amos before beginning the repetition.

Source (Beis Yosef DH v'Chosav Rav): The Gemara (Berachos 30b) says that one who will pray twice in succession (Shacharis and Musaf; or one who must repeat Shemoneh Esreh) must pause between prayers until his mind is settled. The Yerushalmi explains that this is the time to walk four Amos.

Beis Yosef (DH veha'Rashba): The Rashba permits the Shali'ach Tzibur to begin immediately, but says that Ashkenazim wait the time needed to walk four Amos. The Rambam requires waiting longer, but the custom is like the Rashba.

Rema (ibid.): Likewise, one who prays by himself waits this long until returning to his place.

Taz (3): Even in the place where the three steps ended he should not say Tachanun until waiting the time to walk four Amos. (This is about two seconds.)

Mishnah Berurah (11): The Bach and Magen Avraham require an individual to wait the time it takes a Shali'ach Tzibur to reach Kedushah. If one will pray another Tefilah, or in pressed circumstances, it suffices to wait the time to walk four Amos.

Shulchan Aruch (ibid. 3): The three steps after Tefilah begin with the left foot.

Source (Beis Yosef DH v'Chasuv): Medrash Tehilim (Sof Perek 35) says that the three steps after Tefilah begin with the left foot. Orchos Chayim (28) says that the three steps before Tefilah begin with the right foot, because whenever one turns he should turn to the right (Yoma 58b). Also, when one begins to walk he moves his right foot first (Menachos 34a). Sefer ha'Mafte'ach says that we begin the steps back with the right foot. One should follow the Medrash. Turning to the right does not apply here, for he does not turn to either side.

Magen Avraham (10): We begin with the left to show that we are reluctant to depart from the Shechinah. (Similarly, we remove Tefilin Shel Rosh with the left hand.) Therefore, a lefty begins with his weak (right) foot. Some say that we begin with the left to show honor to the Shechinah (it is to the right of the Shechinah; if so, the same applies to a lefty). Some say that three times he steps back with the left and brings his right foot even with his left.

Shulchan Aruch (ibid.): In each step the toe should go even with or in back of the heel.

Beis Yosef (DH Chosav Od): This is how Kohanim walk. Similarly, in each step forward (before Tefilah) the heel should go even with or in front of the toe of the other foot (Orchos Chayim 28).

Bach (DH Mihu): When possible one must take steps this size. When it is cramped one may rely on the Rashba who says that there is no Shi'ur to the size of the steps.

Rebuttal (Magen Avraham 10): The Rashba means that the steps need not be as long as normal steps (an Amah each), but he agrees that less than from toe to heel is not called a step.

Mishnah Berurah (14): Steps smaller than this are not considered steps at all. Poskim argue about whether or not one may be lenient when it is cramped. One may not step back at all into the four Amos in front of someone who is still praying Shemoneh Esre in back of him.

Mishnah Berurah (13): The first step is a half step (for the feet were even at the start). The second step is a full step (the right foot goes from in front to in back), the third step is a half step (he brings the left foot even with the right).

Rema: L'Chatchilah, one should not take steps larger than this.

Source (Magen Avraham 10): This is like Kohanim. Also, one does not want to appear like he runs away from the Shechinah.

Source (Gra DH ul'Chatchilah): It is forbidden to take big steps when leaving a Beis ha'Keneses (Berachos 6b), all the more so after Tefilah.

Shulchan Aruch (ibid. 4): It is haughtiness to take more than three steps.

Taz (7): This is because he shows more honor to the Shechinah than other people do.

Shulchan Aruch (ibid. 5): Also a Shali'ach Tzibur must take three steps when he prays silently, but not after praying out loud.

Magen Avraham (12): If one does so after praying out loud we do not protest.