The Mysterious Ship is the ship upon which S. finds himself shanghaid, captained by Maelstrom. It is an old, battered ship that is said to be comprised of materials from entirely different sources, seemingly referencing the Ship of Theseus thought experiment. The boat is never given a proper name in the series; as such, “Mysterious Ship” is simply a placeholder1).
It seems to have the ability to travel outside of space and time, as S. finds himself emerging in drastically different time periods after spending relatively short amounts of time on the ship. When Vévoda's airplanes appear near the ship during transit, it seems to be of significance; this may mean that the ship, while in transit between goals, is in some outside dimension.
Eventually, S.'s ship is destroyed and its crew killed, but after discovering Sola, S. finds that not only is she a passenger on a different ship of the same design and qualities (with a different crew), but that there are even more ships exactly like theirs. These other ships appear to have the S symbol on their hulls. This is referred to as “the Tradition,” though it is never further explored.