Gaited horses have a gene that allows them to gait. My experience is mostly with Icelandics, so I don't know specifics for other gaited breeds, but I will assume it works similarly. There is a gene they have that allows them to move each leg independently and take longer strides. Try swinging your left arm forwards with your left foot & your right arm forward with your right foot. Most likely, you won't be able to do it or will have a very difficult time doing it. You can get the hang of it if you practice a lot, but it will be very frustrating, challenging, and not a fast or effective way of moving. This is how most horses are. Gaited horses would have no issue, though. In Icelandics, they have an A gene to gait, and it is incomplete dominant. Non gaited horses are CC. Icelandics can have AA, CA, and CC. CC means they are 3 gaited and can't tölt or pace (walk, trot, canter/gallop). These horses are usually eaten and that is why it is not recommended to breed two CA horses together. CA horses are 4 gaited (walk, trot, tölt, canter/gallop). They can't pace, but they can tölt and there is debate on whether their other gaits differ from a 5 gaited horses (some say they have stronger basic gaits, some say worse, I personally don't think there is a noticeable difference). AA horses are 5 gaited (walk, trot, tölt, canter/gallop, pace), but some horses still don't display the pace because it is weak. Most high quality Icelandics have the AA gene.
A CC horse (non gaited) from a gaited breed bred to a non gaited horse (also CC) can't have gaited offspring as all foals will be CC.
A CA horse (4 gaited) bred to a non gaited horse (CC) has a 50% chance of a non gaited foal and a 50% chance for a 4 gaited horse.
A AA horse (5 gaited) bred to a non gaited horse (CC) will always have four gaited offspring.
Video of these gaits