There are many things in Middle-earth which fly. Probably the earliest to be mentioned is the Eagles - messengers of Manwe, maiar embodied. Almost as a mirror of the Eagles, there are the fell beasts on which Sauron mounted his Nazgul - creatures from ancient times, which Tolkien sometimes refered to as pterodactylic. We also have the lesser birds - notably Saruman's crebain, and the ravens of the Lonely Mountain. All of these things have parallels or sources in our own world - in the present or in prehistory.
There are other means of flight in Arda - unnatural ones. And they have three sources:
The Valar
The Valar are noteworthy as the only group in Arda with a space program. First up: the stars. The oldest stars are simply part of creation, but Varda creates new ones. She takes the dew of the Two Trees and scatters them across the heavens. How? Magic, of course - but magic in Middle-earth is not 'point and click'. There is no teleportation that we know of; the dew had to be put in the sky. Were they simply stuck onto the dome of heaven? Perhaps - we don't know if the stars moved before the world was made round. Either way, since we're told Varda put them there in person, she has the honour of being the first astronaut in Arda.
Even if you argue that the pre-elven legends are just magical myth, there is a very definite Valarin Space Program. When the Two Trees died, it took a mere twenty-odd years to create vessels which could lift the Sun and Moon into space, and fly them there. This was guided flight - Tilion notoriously nearly ran into Arien.
Five hundred years later, the Valar used this same knowledge to rebuild Vingilot, the ship of Earendil, into a spacegoing vessel. Earendil was not magical - his ship needed propulsion, and above all, needed to be airtight. Whether or not the Lights were true spaceship, Vingilot was.
And it was armed.
Morgoth
"Then on a time [Morgoth] assembled all his most cunning smiths and sorcerers, and of iron and flame they wrought a host of monsters such as have only at that time been seen and shall not again be till the Great End. Some were all of iron so cunningly linked that they might flow like slow rivers of metal or coil themselves around and above all obstacles before them, and these were filled in their innermost depths with the grimmest of the Orcs with scimitars and spears; others of bronze and copper were given hearts and spirits of blazing fire, and they blasted all that stood before them with the terror of their snorting or trampled whatso escaped the ardour of their breath; yet others were creatures of pure flame that writhed like ropes of molten metal, and they brought to ruin whatever fabric they came nigh, and iron and stone melted before them and became as water..."
These are the dragons, as seen at the Fall of Gondolin - living tanks, troop-carriers, and flamethrowers. Glaurung was one of these - and later, when Morgoth perfected flight, so was Ancalagon the Black, first of the Winged Dragons.
During the turmoil of the War of Wrath, Ancalagon and his winged host - fighter planes and bombers, only far more terrifying, living weapons of unimaginable fury, inpenetrable to arrows or swords - wrought ruin on the Host of the West - until Earendil came. Vingilot was no slow, stately ship, drifting aimlessly through space - it was a gunship, a fighter, dogfighting with dragons and, all by itself, winning. What weapons was it armed with? Was the light of the Silmaril focussed into a holy laser, burning through the dark iron of the dragons?
Who knows. No witnesses to that fight ever set foot on the earth again. But it must have been spectacular.
Numenor
The Edain fought in the War of Wrath. They watched Earendil's battles from afar. And when they moved to Numenor, the threat of dragons or the glory of flight moved them to try and emulate Vingilot.
And they succeeded.
"...they achieved... ships that would sail in the air of breath. And these ships, flying, came also to the lands of the new world, and to the east of the old world; and they reported that the world was round. Therefore many abandoned the Valar and put them out of their legends. But men of Middle-earth looked up with fear and wonder seeing the Númenóreans that descended out of the sky; and they took these mariners of the air to be gods, and some of the Númenóreans were content that this should be so." - The Drowning of Anadûnê
And later - much later - when Sauron came to Numenor, he brought new technologies, a new age - the Numenorean Industrial Revolution:
"Our ships go now without the wind, and many are made of metal that sheareth hidden rocks, and they sink not in calm or storm; but they are no longer fair to look upon. Our towers grow ever stronger and climb ever higher, but beauty they leave behind upon earth. We who have no foes are embattled with impregnable fortresses - and mostly on the West. Our arms are multiplied as if for an agelong war, and men are ceasing to give love or care to the making of other things for use or delight. But our shields are impenetrable, our swords cannot be withstood, our darts are like thunder and pass over leagues unerring." - The Lost Road
Did any of these advances - the works of Steampunk Numenor - survive into the Third Age? Well... maybe. They were long gone by the time of the War of the Ring, but did you ever stop to wonder why Gondor, in all its might, had so much trouble with the tiny Havens of Umbar? Why Umbar managed on more than one occasion to wipe out Gondor's entire fleet, and even, once, to conquer the kingdom? Umbar, for a thousand years the home of the Black Numenoreans - also known as the King's Men, those who had followed Sauron and Pharazon down the road of industrialisation...