Stunt horses have been around for many years...decades...going all the way back to the old westerns.
This type of "fall" takes some time for the horse to learn...
Horsechannel.com : How Stunt Horse are Trained to Fall
Teaching the Fall
Trained falling horses are valuable, and for good reason: It takes a special horse to execute this behavior.
"Think of a falling horse as an acrobat,” says Petrine Mitchum, author of Hollywood Hoofbeats: Trails Blazed Across the Silver Screen. "They need to be athletic and fearless, and also need to have a very trusting nature. So they have to not only have a calm, strong nature but also be willing to place total trust in their trainer.”
Before a horse is asked to fall, the ground is softened with a mixture of dirt, sand and sawdust, according to Mitchum in Hollywood Hoofbeats. With the trainer on the ground, the horse is taught to lie down from a halt. The animal’s left foreleg is tied up, and the trainer stands on the left side of the horse and gently pulls him off balance by pulling the right rein over the saddle. The trainer repeats the process daily until the horse learns the rein cue and no longer needs to have his leg tied. The trainer then teaches the horse to fall with a rider.
"The training is very specialized and not just anyone can do it,” says Mitchum. "It requires extreme patience and confidence, and the ability to read the horse and know what it is capable of, and when to push and when to back off. The trainer also has to have impeccable timing and a certain fearlessness, as well. To deliberately fall down with a 1,000-pound animal in a gallop is not for the faint of heart*.”
* The last part refers to a moving horse but, clearly, a stationary horse would be safer for the stuntperson
So, having trained your horse, it's just a matter of positioning the camera and timing the fake punch to coincide with the horse being commanded to fall down...oh, and a sound effect.
UpRoxx suggests there was more than one horse available
The horse punch, of course, came with some backlash. There were two horses on set that were trained to fall down, but that didn’t stop animal rights activists from sending Mel Brooks and the studio angry letters about the horse punch.