What I've got so far is that somehow the Warsmith may have figured it out, or Flameheart had the knowledge on how to dive, and that's why skeleton ships have been able to, and also why the Servants were given the ability when it was required.
With the Pirate Lord's vast knowledge on artifacts and cursed of the Seas, he got this knowledge in some way and gave it to the Guardians as was required.
After some time, the 'secret' trickled down to the Trading Companies, as regular pirates could have access, and therefore they would be researched.
The problem is that there is no real explanation or tangible object that this relates to. The voyage table menu is just another in a long list of immersion-breaking menus, even if the system is good.
My head-canon is that the Breath of the Sea is how diving is possible, and after turning them in to the Trading Companies for so long, they learned this secret of the Pirate Lord and Flameheart on their own or they worked with the Pirate Lord. I would like to say that the War Map is an item enchanted by a Breath of the Sea, allowing both a ship and her crew to go underwater. It would have been nice if the quest table menu was just an animation of you unfurling the quest map and seeing your options on the scroll, and then having the scroll power the transport. But clearly Rare doesn't think "immersive" and "menu" can exist in the same phrase...