early 15c., replacing forms from Old English fleogende "flying, winged;" present-participle adjective from fly (v.1). The meaning "attached so as to have freedom of movement" (1670s) is the source of the nautical use (flying jib, etc.). Meaning "designed for rapid movement" (especially in military terms, e.g. flying camp) is from 1660s; meaning "passing, hasty, temporary, rapidly constructed" is from 1763.
Flying fish is from 1510s; flying buttress "segment of an arch projecting from a solid mass and serving to stabilize a wall" is from 1660s. Flying Dutchman, ghost ship off the Cape of Good Hope, is attested since 1790 [John MacDonald "Travels in Various Parts of Europe, Asia, and Africa"]. Various accounts are given of how it came to be condemned to sail the sea, beating against head-winds, till the day of judgment. It is said that the ship sometimes hails vessels with the request that they will take letters home.
Flying colors (1706) probably is from the image of a naval vessel with the national flag bravely displayed. Flying machine is from 1736 as a theoretical device. Flying saucer first attested 1947, though the image of saucers for unidentified flying objects is from at least 1880s.