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 Frisianfliata, Old Norsefljóta, 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).