A lot of it comes from conditioning and training the animal to battle conditions along with genetics.
For horses, Kikkuli, the master horse trainer of Hittites in 1345 BCE, described his methods for conditioning horses or chariot warfare in one of the first horse training treatises. His methods aren't too far removed from techniques used today.
Europeans, Mongols and Arabs bred horses specifically for their warfare needs, either swift combat maneuvers or the ability to carry a armored person into battle without fear. Horses that failed to make the grade genetically were moved to farm work or simply eaten.
One legendary horse is Alexander the Great's Bucephalus. This horse was noted for his ability in battle, stamina and ability to survive. The link also mentions Comanche, the only US military survivor, equine or human, from the Battle of the Little Big Horn. Remember though that most horses didn't survive battles.
Dogs were also bred for battle and specifically trained for it. Some breeds are still with us today, such as the mastiff, while other breeds have faded away, like the Alaunt.
During the battle of Marathon, it was related by some historians of the time that at least one hoplite brought his dog with him and the dog fought the Persians alongside him. Like horses, war dogs didn't often survive battles and thus didn't become the stuff of legend, at least by name, until recently.
Even today, most war dogs work in obscurity. One exception is the Belgian Malinois war dog named Cairo that was in on the Navy SEAL's Bin Laden raid.