Flying is a special ability of creatures, which allows them to bypass obstacles (e.g. walls) during combat. Having creatures with this special ability in a hero's army does not affect the movement of that hero on the adventure map in any way (meaning that flying creatures also cause a movement penalty on non-native terrain).
Some other unusual movement abilities, such as the Devil's teleportation, give the same mechanical benefit and are lumped together with flying on this page.
Creatures with this special ability: