I understand that the weight of the player and the player's gear must be within the mounts carry capacity, but is this the only requirement? Are all medium animals with a high enough strength allowed to carry medium sized players? Does the creature need to be trained in the general purpose of riding or combat riding?
A mount must be at least one size larger than the rider. So a medium rider requires a large mount. In addition, a flying mount can only fly with a rider that's within the mounts light load. (DMG 204)
For general purpose riding, training is generally not required. No Ride checks are required either, though if the animal is actively unwilling to bear a rider than your DM can require a Handle Animal check (a wild Dire Bear is probably not just going to let you hop on!).
For combat riding, things change and a Ride check is required if untrained:
Thus, combat riding training is required both to avoid the check, and to avoid using a move action to make the check.
The requirements for a mount are that it is one size category larger than the rider, and that it is capable of carrying the rider’s weight (including any equipment the rider is wearing).
Since size increases and being a quadruped both increase carrying capacity, most mounts have no trouble at all with a rider’s weight. The size category requirement is the primary one.
Aside from that, literally any creature willing to do so can serve as a mount for a creature at least one size category smaller. A DM may inject some reason into this for the cases of creatures that don’t have any apparent place to put a rider despite their size, but then I’m pretty sure there’s a saddle in one of the books for riding a gelatinous cube, so that doesn’t go very far.