Earth dragons are specifically mentioned to have no wings and be unable to fly, so how is Fei able to do so?
From when Araba first shows up:
Contrary to it's name, it looked more like a wolf.
It had four feet that trod on the ground.
A long tail.
No wings.
What I saw there was an imposingly majestic dragon.
This may not have been explained adequately in the anime (or perhaps I just have a knack for not paying attention). Firstly, note that Fei was an earth wyrm, not an earth dragon, and this series makes a distinction between these, as a dragon is a more evolved form (which Fei may reach someday). Now, for the answer.
Fei is able to fly because she evolves into a light wyrm. This is a special evolution that becomes available to her because she's the hero's familiar. From the light novels, volume 3, chapter S6: Hiding:
Fei had evolved, becoming a light wyrm.
Apparently, this new evolution was suddenly available to her because I became the hero.
Since we have a contract as master and familiar, my obtaining the Hero title had an indirect effect on Fei
According to Hyrince, there have been similar cases in the past.
When a hero has a monster familiar, that monster undergoes a a special evolution.
This is how Fei apparently shifted gears from being an earth wyrm to a light wyrm.
With her powers as an earth wyrm still intact.
Earth wyrms are known for their exceptional defense power.
So Fei gets to keep that defense, while gaining the ability to maneuver freely on both land and sky thanks to her new wings.
Her newly acquired skills are Light Wyrm level 9, Light Magic level 1, and Flight level 1.
Though Shun doesn't notice at first, he also figures out Fei has a hard time flying straight since her Flight is still level 1, after he tells her to fly straight at an enemy:
I couldn't tell up until now, but it seems like Fei really isn't used to flying yet, since she hasn't trained the skill up at all.
Apparently, flying straight is even more difficult than dodging the beam attacks.