The Falmari, originally Telerin Elves of Aman under Olwë, and the Falathrim, Elves of the Havens of the Falas in Middle-earth, were masters of ship-building and were great mariners, but not great explorers or formidable sea-powers like Men would become; Elves used their ships mainly for travel, or in later millennia to take the Straight Road over the Sea to Valinor.
It was Men who amassed fleets of ships for the purposes of exploration and war. The Númenóreans were the first Men to venture to sea, and they used ships to explore and colonise Middle-earth in the Second Age. The Guild of Venturers was formed in Númenor by Tar-Aldarion leading to great feats of navigation. After the Downfall of Númenór, the seafaring tradition was passed on to the Dúnedain living in exile in Middle-earth of which Gondor was the most powerful for a time. Gondor's mariners sailed west seeking the Undying Lands, but returned with news that the world had been made round.
In the Fourth Age, Legolas of the Woodland Realm built a ship in order to sail to Valinor from Middle-earth with Gimli the Dwarf, after the death of Aragorn II and the earlier departure of the Ring-bearers.