Gemara

17b - Mishnah: If Yom Tov is on Yom Rishon, we are Tovel everything before Shabbos;

Beis Hillel say, we are Tovel Kelim before Shabbos. People may be Tovel on Shabbos.

18a - Rava: We may not Tovel Kelim on Shabbos because it looks like fixing Kelim.

Question: If so, one should not be Tovel on Shabbos, because it looks like Tikun (he fixes himself)!

Answer: When a person is Tovel it looks like he enters the water to cool off.

Question: This applies to Tevilah in nice water. Why is Tevilah in bad water permitted?

Answer (Rav Nachman bar Yitzchak): Sometimes when it is hot a person enters (even bad) water in which flax was soaked

Question: This applies in summer. Why is Tevilah in winter permitted?

Answer (Rav Nachman bar Yitzchak): Even in winter, sometimes a person comes muddy from the field and enters water.

Question: This applies to Shabbos. Why is Tevilah on Yom Kipur permitted?

Answer (Rava): (Regarding Melachah) we never find anything permitted on Shabbos and forbidden on Yom Kipur. Since it is permitted on Shabbos, it is also permitted on Yom Kipur.

Rishonim

Rambam (Hilchos Shabbos 23:8): A Tamei person may be Tovel on Shabbos, because it looks like he cools himself.

Ra'avad (Ba'alei ha'Nefesh, Sha'ar ha'Tevilah 3:6): The She'altos (96) permits women to be Tovel on Shabbos, relying on Chafifah (shampooing) from before Shabbos or Yom Tov because Tevilah bi'Zmanah Mitzvah. Since nowadays we do not have Tevilah bi'Zmanah Mitzvah, Tevilah on Shabbos is forbidden.

Rebuttal (Beis Yosef YD 199 DH v'Chosav ha'Ra'avad): The She'altos wrote Halachah l'Ma'aseh, and from the days of the Gemara there was not Tevilah bi'Zmanah Mitzvah (Nidah 67b)! Rather, Tevilah at the first opportunity is considered bi'Zmanah.

Maharil (Teshuvos Chodoshim 96): Tevilah is forbidden on Shabbos because we do not bathe on Shabbos, and lest one squeeze hair. Also, where women Tovel in rivers perhaps they will carry a towel or water four Amos in a Karmelis. The Or Zaru'a permits Tevilah on Shabbos and Yom Kipur because Tevilah bi'Zmanah Mitzvah. We hold Ein Mitzvah, so it is forbidden unless it will cause Bitul of Peru u'Rvu or Mitzvas Onah.

Rebuttal (Teshuvas Chasam Sofer YD 196): Even for the light Mitzvah of going to visit one's Rebbi one may walk through water on Shabbos; we do not decree lest he squeeze. The Beis Yosef preferred to bring a proof for Tevilah itself. Tosfos proves this from the Heter for a Nidah to scheme and be Tovel in her clothes in order to be Tovel them. Even though she could be Tovel without her clothes, we do not decree lest she squeeze! The Beis Yosef did not bring this proof. Since she may Tovel them only by wearing them, she will remember not to squeeze them.

Note: At the end of the above Teshuvah, the Maharil himself says that people think that it is forbidden due to bathing and squeezing. Really, we forbid because we do not allow distancing Chafifah from Tevilah needlessly.

Poskim

Shulchan Aruch (OC 326:8): On Shabbos a person may be Tovel to become Tahor.

Magen Avraham (8): Maharil praises the custom of women not to be Tovel on Shabbos Lo bi'Zmanan. The decree not bathe in cold water, lest one squeeze or carry water in Karmelis, applies. Also, it is forbidden to swim (lest one make a Keli that floats to support himself). The Terumas ha'Deshen says that even though the Mordechai forbids bathing in cold water in a Keli, but permits in a river or Mikveh, the custom is to forbid. Even to be Tovel is forbidden, for it looks like Tikun. The Beis Yosef forbids lest one squeeze hair. Nevertheless, it seems that one may be Tovel from Keri, for this is mid'Rabanan (i.e. a mere stringency - Machatzis ha'Shekel).

Mishnah Berurah (24): Even though it is forbidden to be Tovel Kelim on Shabbos because it looks like Tikun, a person may be Tovel because it looks like he cools himself. This is even if it is cold or the water is putrid, for sometimes a person comes muddy from the field and enters water. Therefore, it is permitted even if he could have immersed before Shabbos. It is proper that a woman not be Tovel on Shabbos if it is not bi'Zmanah. Because we do not bathe in cold water, clearly the Tevilah is for Taharah, and it looks like Tikun. Tevilah from Keri is permitted. Since Ezra's enactment was Batel and one may learn Torah and pray even before Tevilah, it does not look like Tikun. Some disagree, but we do not rebuke who is lenient because most Poskim are lenient. Certainly, one who became Tamei on Shabbos or Yom Tov should not be stringent; this is our custom. However, he must be very careful not to squeeze, for this is an absolute Isur.

Kaf ha'Chayim (31): In some places we permit bathing in cold water on Shabbos. One should have a big towel special for this, which he does not mind if it is soaked (so he will not be tempted to squeeze it).

Shulchan Aruch (511:3): On Yom Tov a person may be Tovel to become Tahor.

Kaf ha'Chayim (33): If women cannot be Tovel because the water is too cold, some permit to heat water on Yom Tov to take off the chill, to prevent Bitul of Peru u'Rvu. It is better if a Nochri heats the water.

Rema (YD 197:2): A woman may be Tovel on Shabbos only if her husband is in the city and it is her first opportunity.

Source (Agur and Maharil, brought in Beis Yosef DH Kasuv): A woman may be Tovel on Shabbos (or Motza'ei Shabbos) only if it is her first opportunity.

Rebuttal (Beis Yosef ibid.): Nowadays, women never Tovel at the first opportunity mid'Oraisa, nevertheless they Tovel on Shabbos and Motza'ei Shabbos!

Taz (2,3): Even according to the opinion that Tevilah bi'Zmanah Lav Mitzvah, when her husband is in town it is a Mitzvah because of Peru u'Rvu. The Rema rules that this Mitzvah permits Tevilah on Shabbos.

Rema (128:4): Our custom is to give Birkas Kohanim only on Yom Tov, for then we are b'Simchah.

Magen Avraham (70): The Agor explains that the custom is for Kohanim to be Tovel the day they give Birkas Kohanim, and it is too difficult for them to do so every day. It seems that this is why they do not Duchan when Yom Tov is on Shabbos, to avoid Bitul Onah (marital relations) on Shabbos. It seems that this is why Kohanim avoid relations on Yom Tov. Even after a Ba'al Keri is Tovel, he is a Tevul Yom until the next evening. Also, the custom is not to be Tovel on Yom Tov.

Kaf ha'Chayim (272,273): Kohanim should not avoid relations due to this custom without a source. Birkas Kohanim is a part of Tefilah, which is permitted to a Ba'al Keri. In Eretz Yisrael and Mitzrayim they Duchan every day. Surely they do not refrain from their wives every day! If one wants to be stringent, he should be Tovel the next morning.

Bi'ur Halachah (326:8 DH Adam): Even regarding Kelim, we did not forbid Tevilah when they became Tamei that day, all the more so regarding people! Perhaps the Magen Avraham holds that we are lenient only for the sake of Taharos. Alternatively, we do not permit to become Tamei and to be Tovel on Yom Tov. The Magen Avraham contradicts what he wrote in Siman 326. There is no problem of Tikun regarding Tevilah on Shabbos for extra Taharah, like we permit Tevilah mi'Gav l'Gav (Beitzah 19a). However, the Maharil says that women should not be Tovel on Shabbos Lo bi'Zmanan, due to squeezing. The same applies here.

Kaf ha'Chayim (326:32): It is the custom of Chachamim in Yerushalayim to be Tovel on Shabbos morning. Also the Ari Zal permits.

Kaf ha'Chayim (33): Rav Hai Gaon forbids a Ba'al Keri to be Tovel in hot water on Shabbos. Several Acharonim permit. The Korban Nesan'el (Shabbos, Sof Perek 2 [100]) says that the decree against bathhouses does not apply to Tevilah. Some even permit to add a small amount of water heated from before Shabbos into the Mikveh. One who is stringent not to be Tovel in hot water on Shabbos will be blessed.