Gemara

Mishnah: Anything forbidden because of Shevus on Shabbos is also forbidden on Yom Tov. One may not ride on an animal...

Gemara: It is a decree not to ride on an animal lest one leave the Techum.

Inference: This shows that the Isur of Techumim is mid'Oraisa!

Rejection: Rather, it is a decree lest one break off a branch (an Av Melachah).

Shabbos 94a - Mishnah: If one was Motzi a live person on a bed, he is exempt even for the bed, for it is Batel to the person.

Beraisa: (It is forbidden to sell a large (work) animal to a Nochri, lest on Shabbos the Yisrael show how to make it work, or lest the Yisrael come to rent or lend and transgress letting his animal rest on Shabbos.) Ben Beseira permits a horse because it is normally used for (carrying people,) a Melachah for which one is not Chayav Chatas.

142a - Beraisa: If one was Motzi a clothed person with sandals on his feet and rings on his fingers, he is exempt.

Rishonim

Rif and Rosh (5:2): One may not ride on an animal on Shabbos lest one break off a branch to conduct it (by hitting it).

Rosh (ibid.): The Yerushalmi says that one may not ride on an animal because of Shevisas Behemto (one must let his animal rest on Shabbos).

Rambam (Hilchos Shabbos 21:9): One may not ride on an animal on Shabbos lest one break off a branch to conduct it. One may not alight on an animal from before Shabbos to sit on it on Shabbos. If one climbed up a tree b'Shogeg he may climb down, but not if he climbed up b'Mezid.

Rambam (ibid.): If he alighted on an animal in either case he goes down because it is painful to the animal.

Source #1 (Magid Mishnah): The Rambam extrapolated from the next Halachos he brings (Heterim to unload animals on Shabbos taught at the end of Maseches Shabbos).

Source #2 (Gra OC 305 DH v'Im): He learns from the Yerushalmi in Beitzah.

Rosh (Eruvin 4:3): The Rashbam says that if a Nochri conducts a wagon, a Yisrael riding inside does not transgress, even if they leave the Techum. It appears that it is forbidden because he uses animals on Shabbos. Regarding Kil'ayim, riding in a wagon is like riding on the animal.

Poskim

Shulchan Aruch (OC 305:18): One may not ride on an animal on Shabbos lest one break off a branch to conduct it.

Beis Yosef (DH Ein): The Rosh cites the Yerushalmi that forbids because of Shevisas Behemto. Why is this forbidden? It is not a Melachah, because Ha'Chai Nosei Es Atzmo! Perhaps because it is painful for the animal he transgresses Shevisas Behemto.

Magen Avraham (7): The Shulchan Aruch (below, Sa'if 22) is not concerned for Shevisas Behemto, unlike the Yerushalmi.

Kaf ha'Chayim (63): Olas Shabbos says that according to the opinion that forbids Techumim mid'Oraisa, even someone without hands is forbidden. Tosefes Shabbos suggests that the decree not to use animals applies to everyone, even if he cannot break a branch.

Shulchan Aruch (ibid.): If one alighted on an animal, even b'Mezid, he goes down because it is painful to the animal.

Rema: One may not sit in a wagon conducted by a Nochri because he uses the animals. Also, perhaps he will break off a branch.

Beis Yosef (DH v'Chosvu): Sefer ha'Terumah says that we are not concerned as long as the Nochri conducts, but we are concerned lest the Yisrael leave his Techum, leave the wagon and forget that he may not move outside of four Amos. The Maharik infers that it is permitted within the Techum. However, this is according to the Rashbam (in Tosfos Eruvin 43a DH Halachah). Tosfos (ibid.) and the Rosh (Eruvin 4:3) forbid in any case because he uses the animals, and lest he break off a branch.

Gra (DH Gam): Tosfos says that it is Asur to use animals because he might break off a branch. The Rema means that even those who are not concerned for breaking off a branch (when a Nochri conducts) forbid, for one may not make any use of an animal.

Mishnah Berurah (62): Chachamim decreed not to ride lest one break off a branch. They made a uniform decree and forbade all uses, even when this concern does not apply.

Drishah (3): The text of Tosfos should say 'it is Asur (even when a Nochri conducts), because he uses animals, and (when a Yisrael conducts we are also concerned) lest he break off a branch.'

Magen Avraham (10): Tosfos and the Rosh do not mention the Isur Techumim, because the Yisrael is passive and the Nochri conducts. Some say that all agree that we are concerned for Techumim even when one is passive, like on a ship. Tosfos and the Rosh explain why it is forbidden even inside the Techum.

Mishnah Berurah (66) and Sha'ar ha'Tziyon (58): If a Yisrael conducts the animal it is forbidden mid'Oraisa because of Mechamer (making an animal work) on Shabbos (the wagon is not Batel). He also transgresses Shevisas Behemto if it is his animal. Even if he rented it, some are stringent to say that rental acquires.

Mishnah Berurah (67): The entire wagon is considered Tzidei (the sides, or something attached to a) Behemah, so one may not use it, even a board sticking out of it.

Rema (248:2): (In certain cases one may board a ship within three days before Shabbos.) There is no Isur even if animals on the river bank pull the ship on Shabbos. This is unlike riding in a wagon.

Taz (4): One may not ride in a wagon lest he get off and walk outside his four Amos, transgressing Techumim. This concern does not apply here.

Magen Avraham (9): One may not ride in a wagon lest he break off a branch. Here he would not do so, for he is far from the animals. This is Tzidei Tzedadim of animals, which is permitted.

Rebuttal (of Rema, Taz and Magen Avraham - Korban Nesan'el Beitzah 5:6): The Yerushalmi mentions Shevisas Behemto to forbid even when there is no concern for breaking off a branch, e.g. in a desert or on a boat. This is not considered Tzidei Tzedadim, for he uses the animals. If the animals belong to a Nochri, it is permitted even in a wagon.

Rema (266:2): If one was on the road with a donkey when Shabbos came, he may not ride on it unless there is danger.

Beis Yosef (DH Kasuv b'Sof): Hagahos Mordechai says that it is better to ride on the animal, for just like ha'Chai Nosei Es Atzmo exempts for himself, it exempts for the saddle. If he walks (and causes the animal to follow him) he transgresses Mechamer mid'Oraisa for carrying the saddle. The Mordechai says that one should discard the saddle and walk. We do not permit Shevus for a small loss. Terumas ha'Deshen (61) cites an opinion that it is better to ride, for all agree that this is mid'Rabanan, but some say that Techumim of 12 Mil is mid'Oraisa. However, some say that Techumim apply even above 10 Tefachim, so it does not help to ride. Even the opinion that permits above 10 agrees that if he rides in a wagon four Tefachim wide it is as if he is on the ground, therefore it is better to walk. The Rivash says that as long as one is in the Techum he should walk unless it is dangerous.

Magen Avraham (7): If his feet are within 10 Tefachim of the ground it is as if he is on the ground. Rashi (Eruvin 43a DH b'Amud) connotes that Techumim applies wherever it is convenient to go. This includes riding on an animal or in a wagon.

Mishnah Berurah (10): If he rides in a wagon he is also prone to transgress Mechamer.

Kaf ha'Chayim (25): If one must ride in a wagon on Shabbos to avoid being stranded in a place where he will have to take Tzedakah, he may ride.

Shulchan Aruch (305:22): One may lead his animal to drink even while a Nochri rides on it, because ha'Chai Nosei Es Atzmo.

Beis Yosef (DH Mi): The Mordechai says that because ha'Chai Nosei Es Atzmo, carrying a person is forbidden only mid'Rabanan, and Chachamim did not decree Shevus regarding animals. However, according to the Yerushalmi that forbids because of Shevisas Behemto, it is forbidden.

Shulchan Aruch (ibid.): It is forbidden if the Nochri puts his clothes or anything else on the animal.

Kaf ha'Chayim (96): We are not concerned for the saddle, for it is Batel to the rider. The same applies if he uses one of his garments in place of a saddle.