Maseches Avodah Zarah, Chapter 1, Mishnah 6. The background to this mishnah is the obligation to rest on Shabbos, which applies not only to the Jew himself but even to his animal. The pasuk says: "Uvayom hashevi'i tishbos... lema'an yanuach shorcha vachamorecha" - the ox and the donkey too are required to rest on Shabbos, and it is forbidden from the Torah for a Jew to cause his animal to perform work on his behalf on Shabbos.
The background to the rabbinic decree:
A Jew who cannot use his animal on Shabbos might look to get the full economic value out of it by renting it to a non-Jew for the day of Shabbos - something the Torah forbade. For this reason the Sages issued a broad decree concerning the very trade in work animals, lest a person come to rent them out on Shabbos. They therefore forbade rabbinically to sell a non-Jew a large animal - big animals such as cows and horses, which are likely to be used for work - under any circumstances, so that people would not come to rent out their animals on Shabbos. Our mishnah comes to clarify whether this restriction has additional components.
"Makom shenahagu limkor behemah dakah l'goyim mochrin":
In a place where the custom was to sell a small animal - small animals, goats and sheep - to idolaters, it is permitted to do so. But not everywhere did they agree to this: "Makom shenahagu shelo limkor, ein mochrin" - there were places where the custom spread not to sell even a small animal to non-Jews, and in those places one may not break the custom.
Why was a restriction needed on selling goats and sheep? Two explanations are given:
This is a general restriction that the Sages extended to all animals: just as it is forbidden from the Torah to rent out beasts of burden such as cows and horses, the Sages decreed that one should not sell a non-Jew any animal of his.
In those places that restricted the sale of goats and sheep, the concern was that idolaters are suspected of bestiality, so the sale would cause them to stumble in one of the seven mitzvos of the children of Noach - the prohibition of "lifnei iver". For this reason they refrained from selling any animal at all to their idolatrous neighbors.
"V'chol makom ein mochrin lahem behemah gasah":
Rabbinically, one may never sell an idolater - and in practice any non-Jew - a large animal, such as horses and cows. And not only that, but even "agalim usyachin": a calf is the offspring of a cow, and a colt is the offspring of a horse. These are not generally used as work animals because of their small size, and nevertheless they were forbidden. Two approaches are given for the reason:
The Rambam: They too are fit for light work, such as turning a flour mill.
Rashi: This is a blanket prohibition that included all large animals, and no distinction was drawn between young ones and mature ones.
So too "shleimah ushvurah" - whether the animal is whole and healthy or whether it is broken, such as when its leg was broken. Even though a cow with a broken leg is not going to plow the field, the prohibition against selling it stands. "Rabbi Yehudah matir bishvurah" - in his opinion, an animal whose leg was broken may be sold to a non-Jew, since it is clear that he will not use it for work, as it is damaged and is destined for eating and the like.
"Ben Beseira matir b'sus":
Ben Beseira permits selling horses, because the normal use of a horse is for riding. When a person rides on the horse, the horse is not performing a Torah-level melachah on Shabbos, based on the principle of "chai nosei es atzmo" - a living creature carries at least part of its own weight.
Anyone who has ever carried a child of a decent size knows that when the one being carried does not help by shifting his body in the right direction, the carrying becomes far harder. Hence the expression that distinguishes carrying a live person from carrying "dead weight," which feels immeasurably heavier. This does not mean that if Reuven carries Shimon and they stand on a scale, the number displayed will change depending on whether Shimon is alive or dead; rather, the cooperation of the one being carried in shifting his weight makes a great difference. Therefore, since a living being carries part of its own weight, there is no Torah prohibition of performing a melachah here, and by strict law it is permitted to carry a live person on Shabbos. So too, a horse carrying its live rider is not performing a Torah prohibition, and in Ben Beseira's view the Sages did not issue a decree in such a case.
However, although the principle of "chai nosei es atzmo" is agreed upon by all, and the Tanna Kamma accepts it as well, that does not mean it applies to creatures that are not human beings. The concern is, for example, a horse used for a hunting excursion, with the hunting falcons perched on its back: they are indeed living creatures, but they are not human beings who shift their weight, and so the horse is genuinely carrying them. For this reason the Tanna Kamma forbids it.
The practical halachah:
The Shulchan Aruch states as an obvious matter that nowadays people do sell their animals. It is certainly permitted when the sale is conducted through a middleman - a sarsur - who arranges it (a sales agent, which is not comparable to a rental agent). In any case, for reasons that go beyond the scope of our discussion here, the practice is in fact to sell animals to non-Jews, even a large animal.