Meaning "to glide away like a stream, vanish imperceptibly" is from c. 1200; hence "to fade, to vanish" (1570s). Related: Fleeted; fleeting.
Old English fleot "a ship, a raft, a floating vessel," also, collectively, "means of sea travel; boats generally," from fleotan "to float, swim," from Proto-Germanic *fleutanan(source also of Old Saxon fliotan, Old Frisian fliata, Old Norse fljta, Old High German fliozzan, Middle Dutch vlieten "to flow"), from PIE *pleud-, extended form of root *pleu- "to flow."
The sense of "naval force, group of ships under one command" is in late Old English. The more usual Old English word was flota "a ship," also "a fleet; a sailor." The fleet for "the navy" is attested by 1712. The Old English word also meant "estuary, inlet, flow of water," especially the one into the Thames near Ludgate Hill, which lent its name to Fleet Street (home of newspaper and magazine houses, hence its use metonymically for "the English press" since at least 1882) and Fleet prison (long used for debtors).
It forms all or part of: fletcher; fledge; flee; fleet (adj.) "swift;" fleet (n.2) "group of ships under one command;" fleet (v.) "to float, drift; flow, run;" fleeting; flight (n.1) "act of flying;" flight (n.2) "act of fleeing;" flit; float; flood; flotsam; flotilla; flow; flue; flugelhorn; fluster; flutter; fly (v.1) "move through the air with wings;" fly (n.) "winged insect;" fowl; plover; Pluto; plutocracy; pluvial; pneumo-; pneumonia; pneumonic; pulmonary.
It is the hypothetical source of/evidence for its existence is provided by: Sanskrit plavate "navigates, swims;" Greek plynein "to wash," plein "to navigate," ploein "to float, swim," plotos "floating, navigable," pyelos "trough, basin;" Latin plovere "to rain," pluvius "rainy;" Armenian luanam "I wash;" Old English flowan "to flow;" Old Church Slavonic plovo "to flow, navigate;" Lithuanian pilu, pilti "to pour out," plauju, plauti "to swim, rinse."
mid-14c., navie, "fleet of ships," especially for purposes of war, from Old French navie "fleet; ship," from Latin navigia, plural of navigium "vessel, boat," from navis "ship," from PIE root *nau- "boat."
Meaning "a nation's collective, organized sea power" is from 1530s. The Old English words were sciphere (usually of Viking invaders) and scipfierd (usually of the home defenses). Navy blue was the color of the British naval uniform. Navy bean attested from 1856, so called because they were grown to be used by the Navy. Navy-yard "government dockyard," in the U.S. "a dockyard where government ships are built or repaired" is by 1842.