Gait is affected by a great number of things. One of the first things to look at is the training of a horse, he has to work well on the reins, loose, light, and responsive. Second is flexibility, he must bend well and be able to give his head right and left on a light line. 
Those are the major considerations after that is:

• Saddle placement, by moving your saddle forward or back you can change the way of traveling.
• Use of shoes and hoof angles can change the speed of the "adjusted" hoof. Low angles will slow footfall and increase the length of the stride, high angles will speed the footfall and shorten the stride. Shoes in front will help a pacey horse move more toward gait. Shoes in back will help a trotty horse. 
• It will be much easier for your horse to gait if his hindquarters are engaged. 
• Head and neck carriage is also something to look at if a head and neck are too high he will be too light on the front, or the reverse if his head is too low that shifts weight forward and he will be too heavy on his front end and this will make it difficult for him to engage his hind quarters. Horses use their neck for balance, with this in mind to change your horse's head and neck carriage will change his gait. If he has a tendency to drop his head and neck when you are on the trails, this will shift weight forward and change the way he gaits. 

Remember to ask yourself these questions as you work to improve the gait in your horse:

• "What is happening?"
• "What needs to be changed?"
• "What is the horse trying to tell you right now?"
• "How do you know?"
• "What do you need to do?"
• "How is what you're doing now different from what you were doing before?"
• "What happened when you ..."
• "What difference did you notice?"

Any horse, included Gaited Horses, must be athletes to accomplish many of the tasks their owners request of them. Most people realize this when they are asking their horses to do endurance riding or cross country jumping, but do not equate the need to be an athlete with the "regular Horse". This is why many owners fail to see the need for conditioning is in the horse maintained for pleasure. The "couch potato" of the equine world is the way a friend of mine would refer to these equines. The term couch potato does in fact apply to many of the horses maintained across our nation. They are stabled or pastured for 5 days of the week and ridden one or two days of the week. Even the horse that is ridden more frequently than twice a week, has to have conditioning to perform at their optimum.

There are articles in abundance that address the basic conditioning for a fit equine, so we will not go into those here. For purposes of the information provided, we will assume that your horse is in fit condition. If he is not you should get him that way or the suggestions will not have as good an effect. Avoid doing anything that will hurt your horse mentally or physically, make sure they are ready for what you ask of them.

If you get your horse in shape before you request that he gait under saddle, he is much less likely to start pacing  or trotting. Spend a couple of months getting your horse "legged up" and in condition before you start requiring that he gait consistently under saddle. Remember that the younger horses, with undeveloped muscles will be more likely to pace or miss gait. Make sure that the horses is physically mature before you put him to work. It would also be a good idea if you can RECOGNIZE gait when the horse performs it.  You must be ready to encourage the horse to continue performing gait. 
WORKING WITH GAITED HORSES  by Lee Ziegler is a MUST read!

Lounging

Lounge at the tempo that encourages gait -- pushing the ordinary walk for a little speed.  Ask a trotty horse to lounge with his head a bit higher than usual (not using side reins, using intermittent lifts of the line). Work  on a slanted lounging area, asking for a faster walk downhill, and checking before it becomes a trot or pace.  (you can get a fox trot that way with many non-gaited horses)  Push the fast walk, then use the line to tug the horse's  head and neck toward you, then release it to return to the straight position. With enough working to break up the trot of this type, you can often produce a stepping pace in a hard trotter.

A horse should not be  worked for longer than 10 minutes on one side, 

• Do not  work for more than two circuits in the same gait (walk/intermediate transitions are very good but endless circles at the trot are counterproductive) 
• Use large (at least 30 ft diameter) circles, then spiral them in smaller from time to time.
• Never work on excessively hard or deep footing. 
• Work on a slack line, asking the horse to curve his body around the circle, *never* work on a taut line while allowing the horse to cock his head and neck to the outside of the circle.

Riding

Long and slow rides at a walk and occasional gait for several months, over gradually increasing distance is the ticket for the young horses. Riding down and up hills asking for a speed slightly more than a walk but not accept a trot will encourage the horse to engage their back end and get the stride reaching underneath them better. Riding over very rough ground (i.e. plowed fields, marshy areas or tall grass) will also help a horse to shift their weight back and engage. Flexing exercises performed at the walk, flatwalk, corto or slow rack will help to condition the horse to engage the hindquarters and be able to maintain a balanced gait.  Don't overdo and wear out your horse, build him up gradually. Don't worry about headset too much, ride from your seat and legs, leave the horse's mouth alone as much as possible. 

Horses develop evasive habits to our habits in riding, so the more we are aware of what OUR habits are, and how to relax out of them, the better our horse's chances are of getting some clear communication from us. Riding tense will cause the horse to hollow his back - as your stiff posture compounds the concussion on his spine. In hollowing his back to protect from your bouncing (because you're not relaxed), the horse generally raises his head, throws most of his weight to his shoulders, and "falls out behind" (doesn't track under, goes inverted). Practice riding from your seat and legs, spend a couple of rides in the ring, alone with your horse, and use your legs and seat only to turn and halt. Get a real feel for how much is just enough, not to too much or not enough.
See: The Seat and getting the horse on the bit.  Horses and riders need FOUNDATIONS in training - building blocks, stepping stones, plateaus along the mountain path, in order to fully understand the process of gaited 
riding.
You want the horse to learn to move undersaddle in balance. It's like commanding someone you see on the street to  perform like in the "River Dance", they can't  - it takes allot of strengthening, and a ton of practice, and in time, they can master it.  Once your horse gets the feel for "going balanced"  he will WANT to stay there. 

Flexibility

I once had a respected Paso Fino Trainer tell me that "just because your horse is bending, doesn't mean he is flexing properly." He confused me totally at the time. Wasn't  bending and flexing the SAME thing? Well after many years of studying the horses who DO Flex properly, I can tell you they are NOT the same thing. But a horse has to begin to learn to flex by first being willing to bend.

So how do you teach a horse to bend? One way to begin is to teach him to stretch his neck forward and to the side. These exercises are often accomplished best when a reward is offered, and have become popularly known as "carrot stretches".  Many horses have limited lateral flexibility in their necks. The Carrot Stretch is an exercise to get the horse to begin to stretch and bend the muscles in his neck to prepare to achieve lateral flexibility.

From the ground and working  in a halter or Jaquima. 
 

This Jaquima is made of sturdy leather, double stitched and reinforced at the stress points. The cheek pieces have snaps to make switching out the bosal and chin strap ( or barrbada) easily accomplished. The bozal ( nose band) can be changed out to many different types, as can the barrbada (Chin strap). The Jaquima works off the nose, chin and poll, teaching the horse to seek the point of "no contact" as the correct spot for carriage. This equipment can be made very mild by the choices of Bozal/Barrbada combination or more severe with other choices. The knowledgeable Trainer or Owner seeks the most mild equipment that will cause the horse to work well. This Jaquima is manufactured for Paso Fino, the brow bands tend to be a bit narrow for larger headed horses. You need to measure the brow band and make sure it will work on your horse or be prepared to replace it if you want to use Paso Tack on the TWH, MFT, RMH and some of the other breeds who's heads are larger than the Paso Fino.

The examples on the left are styles of bosals that can be used in the above Jaquima. The first set is made up of a doubled leather strap, one with a lounging ring on the top of the nose, and the other plain. The second set of images is two styles of Barrbada, the piece that goes under the chin. The third set of images are bosals with ball bearings inset to aid in control of the horse. The ball bearings are different sizes, the larger giving the most control. The bumps of the bearings are set to allow contact with sensitive pressure points on the horses nose.

Stand with the horse on your right.  Face the horse and stand at the horse's shoulder. With your left hand grasp the nose band at the side piece, and gently bring the horses nose to the side, insisting that he keep his body still (often placing your free right  hand on the withers will help in this). Ask him to bend just a few inches away from a resting position, pet him, then repeat on the other side. Now you begin to use a carrot as a bribe, holding it in front of his nose and tempting him with it until he follows it around, not giving him the carrot until he bends as far as you want.  He should be bending his neck just a bit farther each time you work with him, until he can touch his nose to his side, on both sides. With many horses this will take several lessons. You do not want  to force him to bend, but to gradually encourage him to stretch the muscles in his neck so that it becomes easy. You should not progress to the saddle until the horse is bending freely to each side, touching his nose about where your knee would be if you were on him.

From the saddle and working in a bosal or Jaquima. Set the headgear up so that the bozal is just above the soft tissue of the nose. The chin strap have it loose enough to put two fingers between the chin strap and his jaw. Put one set of lines on the bozal and the other on the chin strap.  Make sure you have your weight carried balanced on the horse. Take both reins in your right hand, so that you have LIGHT contact with the horse's headgear. Now reach about halfway down the left rein with your left hand and call the horses head to his side with a series of tugs and releases. Switch hands and repeat to the other side. At this point he should be keeping his body still.

To start working on the horse in motion move to an enclosed area . Start by just walking loose and easy if he rushes stop him HARD, let him stand and start walking again with loose lines. When you ask a horse to stand, he should not move. If the horse is resting, he has to make two changes to move off, first he has to prepare to move off by shifting up forward, engaging his hindquarters and lifting his back, second, he actually steps. be prepared to notice these subtle changes so you can anticipate his movement and be ready with the correction. He should move out ONLY when you ask him to.

Getting a horse to react to leg aids can be started from the ground, even before its time to mount them.  While you groom your horse, stroke his sides, and with a tap from your hand at the girth, say: "move over". Praise the horse for doing so. Teach him with "in hand" work by showing them how to move away from the leg, or the whip. You can teach your horse to turn on the forehand, and shoulder in as well from the ground.

When you have the horse understanding the basics of leg aids mount your horse and ask him to stand quietly for at least 20 seconds. Now pick up the reins and ask the horse to bend  and move its hips away from the direction of the bend. Repeat this request many times until yielding the hips becomes a smooth, easy response.  Control of the hindquarters is achieved through leg aids.  Get your horse walking along in an easy going walk.  Now pick up the rein and ask the horse to yield his hip while walking.  At first it will help you both to learn this if you look back at the inside hip.  You want to see the point of the hip swing away from the direction of the bend. That means if your on the left rein and using the left leg to cue, you want to see the hip swing to the right.  The instant that you see even a little movement,  release the rein and stop cueing. The horse associates whatever it was doing at the exact moment of release as the correct response.

To control the hindquarters from swinging out while working in a circle, you "block" the horse hindquarters with your leg. In other words if the horse is circling to the left, and his hindquarters are swinging out of the circle, you would use pressure from your right leg to "Block" the hindquarters from swinging. Remember to give the cue with your lower calf, heels down, with a push and release, not a constant push. It doesn't take any longer to train them to move away from a light cue than a firm one, so keep your cues as light as possible. In the process you will  find that the jaw, neck, and shoulders will have softened as well. Instead of riding a braced, rigid, pulls - like - a - freight train horse, you'll find that your sitting on a light, soft, relaxed horse.

Walk a lot of circles relaxed 5 or 10 ft in dia. be sure to ask ask him to bend his whole body, head to tail. Most horses will be stiff somewhere, most will be in the shoulder that is where most people have the biggest problems. Walk circles, straight, stop, back, and anything else you want to do but all from the walk and on a  loose line. If he starts to pull or want to rush ahead then stop him then stand and start over. 

For the horse that wants to lean into the headgear , start working more on the chin strap. Be as easy as  you can but as hard as you have to. The chin strap will give you more control than the bozal,  you will use it more for bending, and flexing. Slow and easy work on getting the horse to be relaxed, flexible, and light on the lines. Take your time don't rush in the circles, work on being able to move his shoulders in and out. 

If he swings his hindquarter when you start that is ok. But you are after a nice clean even circle always stay light on the lines. Be as soft as you can but as hard as you have to be. As he is able to relax better in the flexing and bending,  ask him to work at a slow gait speed don't worry about what gait just get him easy and light and not rushing. Work a little bigger circles still asking to bend  moving his shoulder and not swing his hindquarters. Use the indirect line to support and keep the head and neck straight, by moving it slightly across the neck. Sit square, and not give any extra pressure on  either seat bone - just the lower leg and light rein cue. 

As  he relaxes better and you can move him forward in a slow gait if he is not rushing or pulling on the lines ask him to come together a little, just put a light contact on the lines and gently push his hindquarter up under him with your legs. The most important part to remember is get him loose and light, then you will be able to ask him to drive off his hind quarters with out pulling or trying to rush.  SOLID Gait is dependent upon 1) the horse's lightness to the reins, 2) timing, and 3) impulsion that is instantly accessible without having to be constantly "driving" the horse with seat and leg.
 

Rein cues are important to achieve flexibility:

• The direct rein focuses the weight on to the foreleg on that rein.  In other words the  right direct rein focuses the horse's weight onto the right foreleg.  If you ground that leg and the horse is moving then his haunches are going to tend to move to the left.  Turn on the forehand.

• The indirect rein focuses the weight on the opposite hind leg.  So a right indirect rein is going to act on the LEFT hind leg. With the weight on the left hind the shoulders can easily be brought left.  Turn on the haunches.

BRINGING the FOREQUARTERS ACROSS

This exercise will  encourage the horse to lighten the forehand which is necessary for almost all gaited work; to develop control of the forequarters independently from the hindquarters and will build the rider's coordination in moving the horse's legs with precision

With the horse standing still and balanced, reach way down the left rein and bring the horse's head gently around toward your knee, just as you did in the earlier flexing and bending exercises. Again, his feet should stay in place. Apply a light rein pressure toward your hips to rock the horse's weight back slightly, while his feet still stay in place, then come in with the "supporting indirect  rein" (right rein coming lightly stretched across his neck but not crossing over his withers). You want to put your weight on the horses left hind,  sometimes it helps by looking at that hip yourself and shifting your weight to that seat bone. Press your  right leg in front of the girth and open up the left rein like a leading rein to give the horse a clear path to move. If the hindquarters are weighted (he was rocked back properly), the forequarters will come loose and he'll step over cleanly in front. It sometimes helps if at  the moment of asking for the forequarters to come across, you use a flag on the right side to encourage the horse to move lightly to the left. The flag enables the rider to teach the horse to make a very, very light turn with a clear moment of front suspension in the step across--without being in his face at all.
 

Remember you are teaching, so take you time. If it take a week or a month it does not matter the end result is was is important. Be content with small progress, get him to relax, have a regular rhythm, and eventually seek the contact of the rein.