Gemara

(Beraisa): We anoint kings only by a spring, for a Siman (omen) that their kingship should last - "v'Horadetem Oso El Gichon; u'Mashach Oso Sham."

(Abaye): Since we learned that omens are significant, on Rosh Hashanah one should eat gourds, fenugreek (or clover), leeks, beets and dates.

Rav Mesharshiya (to his sons): You should learn by a river, so your teachings will endure like a river;

Yalkut Shimoni (Vayera 99): It is not so far (from Be'er Sheva to Yerushalayim). Why did it take Avraham three days to reach the place of the Akedah? Rather, since Avraham and Yitzchak did not heed the Satan, the Satan made himself like a great river in front of them, so they could not pass. The water was up to their necks. Avraham said "You asked me to offer my son. I did not refrain. Now, "Ba'u Mayim Ad Nafesh"! If my son will drown, how will he make Your name One?!' Immediately, Hash-m rebuked the Satan, and the Satan departed.

Rishonim

Maharil (Hilchos Rosh Hashanah 9): Mahari Segel says that on Rosh Hashanah, the custom is to go after the (day) meal to seas and rivers to cast into the depth all our sins. The Medrash says that this commemorates the Akedah, in which Avraham passed through water up to his neck, and said "Hoshi'ah Hash-m Ki Ba'u Mayim Ad Nafesh.' Mahari Segel used to go to rivers. He said that when one goes on Yom Tov, he should not take any food to throw to the fish to make them happy, for this is Chilul Yom Tov. Even if a Nochri is there, he should not take bread from him to throw to the fish. Since they need to be trapped (to benefit from them), they are Muktzeh. On Yom Tov, one may feed only beings that he may use. If he takes food to there, he transgresses carrying outside the Eruv and feeding Muktzeh. All the more so when Rosh Hashanah is Shabbos, he should not do so!

Tosfos (Pesachim 105a DH v'Hani): The Medrash says that one who drinks water Bein ha'Shemashos on Shabbos steals from his dead relatives. With difficulty, they permitted eating after Viduy on Erev Yom Kipur, due to drunkenness.

Mordechai (Tosefes me'Arvei Pesachim 611): The Medrash says that one who drinks water at Minchah (on Shabbos) steals from the (relatives of) the dead, for they drink when they want to return to their Din.

Chasam Sofer (105a DH v'Hani): This is because the dead go to the river before they are judged, just like the living go on their day of judgment to say Tashlich and arouse Supreme Chesed, which is compared to water. Tosfos mentions not drinking water after Minchah on Erev Yom Kipur, since the Magen Avraham says that also the dead are judged on Yom Kipur.

Note: Perhaps he explains that Tosfos does not mean that drunkenness is a reason to forbid eating then. Rather, Chachamim permitted eating after Viduy, for if people would eat before Viduy, perhaps they will be drunk and omit Viduy or say it improperly. Perhaps we are not so concerned lest people eat after Viduy on Erev Yom Kipur and get drunk and omit Viduy at night, for they already confessed.

Leket Yosher: He (the Terumas ha'Deshen) was not so insistent if he did not go to Tashlich. Sometimes he went.

Poskim

Shulchan Aruch (OC 583:2): On Rosh Hashanah, we go to the river to say the verse "v'Sashlich bi'Mtzulos Yam Kol Chatosam..."

Darchei Moshe (2): Minhagim adds that we see live fish. This is a Siman that Ayin Ra'ah should not rule over us, and we should multiply like fish.

Elef ha'Magen (on Mateh Efrayim, 598:8): Fish have no Gvinim. Their eyes are always open. This arouses the seeing eye above to have mercy on us. Also, we are compared to fish caught in a trap; we are in a mortal trap and judgment. This helps one repent.

Magen Avraham (5): In Kesavim (Pri Etz Chayim Shofar 5), it says 'a river or well.' It is good if it is outside the city. One should go on the first day after Minchah, before sunset, and say "Mi Kel Kamocha..."

Ma'aseh Rav (202, in Sidur ha'Gra p.528): The Gra did not go to water to say Tashlich.

Gra (DH v'Holchin): Tashlich is to commemorate the Akedah.

Birkei Yosef (6): Gurei ha'Ari Zal write that one should go on the first day. If the first day is Shabbos, the Ramaz says to go on the second day. (Even if the first day was not Shabbos,) if one did not go on the first day, he goes on the second day after Minchah.

Ha'arah (6): In Machazik Berachah, the Chida (author of Birkei Yosef) said that one may say it on Shabbos. In Yosef Ometz (17:3), the Chida refuted Shevus Yakov, who criticized those who do not say it on Shabbos. Yosef Ometz says that perhaps based on Kabalah, one should not say it on Shabbos. It is better to be passive (and not say it on Shabbos). Elsewhere, the Chida said that we heed secrets that the Ramaz revealed only if they came from the Ari Zal. Here, the Chida understands the Ari Zal like the Ramaz says. I am not worthy to decide a matter that Gedolim argued about, but I cannot fathom that when Rosh Hashanah is on Shabbos, Chachamim uprooted the Torah Mitzvah of Shofar lest one carry it four Amos, but for a custom without any source in the Gemara, people made a custom to say it on Shabbos. The masses carry Machzorim into Reshus ha'Rabim or Karmelis. They say Tefilos that the Chida composed, against his ruling that they not say so on Shabbos! Initially, people said only the verse "Mi Kel Kamocha", so they did not need Machzorim. Nowadays that we say so many additions, it is impossible without a Sidur. It would be great if someone would stop the custom (to say it on Shabbos).

Kaf ha'Chayim (30): In Yosef Ometz, the Chida retracted to say that it is best to be passive. Many defend the custom to be say Tashlich on Shabbos. Even those who forbid would permit within the walls of Yerushalayim, for there is no concern for carrying.

Mishnah Berurah (8): We say "Tashuv Terachamenu..." In some places, if the first day is on Shabbos, they go on the second day. Perhaps this is because the river is outside the city, and people carry Seforim.

Torah Lishmah (145) and She'arim ha'Metzuyanim b'Halachah (129:28): One who cannot go on Rosh Hashanah may go until Yom Kipur.

Mateh Efrayim (598:4): The custom is to go after Minchah to a river or well and read Halichos Tashlich, for it says "v'Sashlich bi'Mtzulos Yam..." We go after Minchah before Shki'ah. If the sun already set, one may go until the night. We shake the bottom of the garments, for a hint to put one's heart to cast off sins and seek ways from now and onwards that his garments be white and clean from all sin.

Elef ha'Magen (9): This refers only to garments with Tzitzis.

Elef ha'Magen (5): The river is a hint that Hash-m recall for us the merit of the Akedah. Also, we coronate Hash-m to be our king, and the custom is to coronate by a river for a Siman that the kingship last. Also, the Targum of the verse "va'Yish'avu Mayim va'Yishpechu Lifnei Hash-m" (Shmuel 1:7:6) is "they will spill their hearts in Teshuvah in front of Hash-m." Rashi explains that this is a sign of humility - 'in front of You, I am like this water that spills...'

Yechaveh Da'as (1:56): Sidur Ohalei Yakov (Rosh Hashanah 149b) says that this is like the custom to anoint kings near rivers so their kingship will last. Rav Mesharshiya told his sons to learn near a rover, so their memory of the text would last and they not forget it. On Rosh Hashanah we do many things for a good Siman on Rosh Hashanah. We go to a river for a Siman that Hash-m's Chesed and mercy on us continue, and He inscribe us for a good year.

Mateh Efrayim (7): If one thinks that he will not have time to go to Tashlich after Minchah, he should go before Minchah,

Elef la'Mateh (3): The Shulchan Aruch and Levush did not mention after Minchah. They connote that one should go before Minchah. However, they say in the name of the Ari Zal to go after Minchah. It seems that we are not so particular about this.

Si'ach Yitzchak (277): One need not wash his hands for Tashlich, since it is right after Minchah and one washed before Minchah. The Maharil says to go after the meal (before Minchah), and the Levush says to go after Musaf before eating! Those who go before Minchah hold that Tashlich is to commemorate the Akedah, and the Akedah was before Yitzchak established Tefilas Minchah. According to the other reasons given for Tashlich, one may go after Minchah. This is the custom in most places. Asarah Ma'amaros says that the Akedah was at (the time of) Minchah. When there is a Bris Milah on Rosh Hashanah, it must be before the Teki'os (Beis Yosef Sof Siman 584, citing Terumas ha'Deshen 266), because Avraham's Bris preceded the Akedah (and the Teki'os commemorate the Akedah). Those are Mitzvos, therefore we are particular about the order. Tashlich is a mere custom, so we are not so concerned about the order. I later saw in the source (the Agudah citing the Mordechai) other reasons why the Bris must precede the Teki'os. The fact that Avraham's Bris preceded the Akedah was a mere supplementary reason.

Kaf ha'Chayim (34): The Ben Ish Chai holds that if one did not go on the first day, he goes after Musaf on the second day.

Kaf ha'Chayim (30): "Mi Kel Kamocha..." corresponds to the 13 Midos of mercy. We ask that our sins, i.e. the Klipos (shells of Tum'ah) created through our sins be cast away, and also the supreme prosecutor should be cast to the depth. One shakes the bottom of our garment, to arouse Klipos to be shaken off the root of his Neshamah above. One can say Tashlich even at a pit without water.

Aruch ha'Shulchan (4): Women should not go to Tashlich. Where they go, men should not go at all.

Elef ha'Magen (7): Women should not go to Tashlich. This leads to mixing of men and women. It gives the Satan opportunity to prosecute on this Kadosh day, reverses advocates to prosecutors, and the Din can be sealed for guilt. The leaders must supervise. If they can stop the custom, they must.