[Maédhros]

A brief skim through "The Istari" in UT did not give me any information about how they traveled; it only says that they came to Middle-earth.

From Unfinished Tales: The Istari

Yet they were not so. For they came from over the Sea out of the Uttermost West; though this was for long known only to Círdan, Guardian of the Third Ring, master of the Grey Havens, who saw their landings upon the western shores. Emissaries they were from Lords of the West, the Valar, who still took counsel for the governance of Middle-earth, and when the shadow of Sauron began first to stir again took this means of resisting him. For with the consent of Eru they sent members of their own high order, but clad in bodies of as of Men, real and not feigned, but subject to the fears and pains and weariness of earth, able to hunger and thirst and be slain; though because of their noble spirits they did not die, and aged only by the cares and labours of many long years. And this the Valar did, desiring to amend the errors of old, especially that they had attempted to guard and seclude the Eldar by their own might and glory fully revealed; whereas now their emissaries were forbidden to reveal themselves in forms of majesty, or to seek to rule the wills of Men and Elves by open display of power, but coming in shapes weak and humble were bidden to advise and persuade Men and Elves to good,

If Círdan saw the landings of the Istari, and the Istari were forbidden to reveal their true forms, then I would think that the Istari travelled to ME from Valinórë they had already their incarnate shapes and travelled in a Telerin ship.

The Ainur are similar to Judaic/Christian angels, with some elements of mythological heathen gods thrown in. Angels are generally perceived as winged, though there is little (perhaps even no? I'd have to look it up to be sure...) actual mention of that in the Bible. The reason for that notion is their ability to travel quickly, going back and forth from heaven to earth, or location to location, in almost no time. As to the mythological gods, there are some who are winged, most notably Mercury/Hermes. I assume that fast, airborne transportation would be the reason for that as well.

If the Ainur are by their nature ëalars, why would they need wings to travel with wings instead of just "moving as spirits". What I concur from this, is that the Valar and the Maiar clothed themselves in certain situations to interact with the Mirröanwi, why would they need wings?
To me the question would be, why would they need for if they can travel with their "spirits". (Like Sauron did when his hröa was destroyed in Númenórë)