A simple change is when the horse changes canter lead through the walk. In dressage, we want the horse to canter balanced, stay engaged into the walk transition, walk no more than 3 steps, and pick up canter immediately on the other lead.
A flying change is more advanced. We want the horse to have a very solid counter canter, and simple changes before attempting the flying change. Different disciplines teach and expect different versions of a flying change. In dressage, we want the horse to collect, 'skip' onto the other lead, and canter collected on the new lead. Once single flying changes are established, we then start on tempi changes - a flying change every 4th, 3rd, 2nd and then every stride as you see in Grand Prix Dressage.
As for training, we, from a dressage perspective again, you want to have all of your basics very established. As said above, you'll want counter canter, simple changes, shoulder in, travers and the horse with a good ability to collect in the canter. They can be taught a number of ways, depending on the horse. Some will change clean the first time you ask them going on a straight line across the diagonal. Others are better if you ask on a serpentine from counter canter, or on a circle from counter canter.
You want to set the horse up for success. Make sure they are balanced, in collection and in front of the leg. When asking, a series of half halts to prepare the horse, then change the flow of your weight, put your new outside leg back, and change the bend.
Sounds simple, and this is broken down to basic, basic, basics! But flying changes are really quite difficult to train. Many horses will change late behind, occassionally late in front, some will panic and run away if they are not ready for it, etc.
I know some disciplines train by cantering over poles, and this is great for a 'functional' change, say as a show jumper, but it often encourages the horse to be late behind, so we do not use this method when training the dressage horse.