Actually, there are several ways to do this. First, you'd want the figure to be light, no heavier than a Rahkshi.
You could have propellers on the figure's back, and pull a rip-cord (Rhotuka-esque) to make the propellers spin quickly, giving the figure enough of a lift to make it fly and hover for a second. Toys based on this idea were released around the time of Matoro's death, and I used to have several. They were called Dragon Flyers or something I believe.
You could also give the figure fold out wings. The wingspan would need to be three times the figure's height. (So for a Glatorian, you'd need an almost three-foot wingspan. Nuva, however, standing at about six inches tall, would only need a one and a half foot wingspan.) The idea here is that the figure would be thrown, and would glide on its folded out wings. Ideally, most of this figure's armor is rubber, as it would inevitably crash into a wall, desk, or priceless antique lamp.
Yet a further method would be to incorporate a motor to flap aforementioned fold out wings. Bird models have been made using this principle, albeit they fly rather fast.
An added bonus to this is that it would reduce the weight, (and therefore, material) of the figure, increasing Lego's profits. I have previously stated on here I believe the weight of each G2 figures contributed to its untimely demise.
Wings/ propellers will work fine. Trust me or read the above.