Years ago, I too thought it related to the (hopefully) circular nature of ship's journey and was symbolic of a ship's return to port. However, I had never read or heard this explanation in Japanese. While the reason that many modern ship names are appended with maru is quite clearly due to a Meji-era law (船舶ノ名称ニハ成ルベク其ノ末尾ニ丸ノ字ヲ附セシムベシ - Whenever possible, ship names should be ended with the character "maru"), nobody knows the exact origin of maru.
So I started searching in Japanese for explanations and kept track of the frequency that a particular explanation was cited. Finally, after wasting much time that could have been better spent whining about softbank, I came up with my own theory, the Poop Hypothesis.
According to the Poop Hypothesis, the original Japanese for poop, maro, was changed to maru in the year 1187 due the spherical nature of "the floater." Ship builders in ancient Japan, a superstitious lot who were notoriously bad at their jobs, were absolutely incapable of accepting the fact that their ships simply did not float. Rather, they chose to believe that the nefarious yet relatively foolish Demons of Sinking (沈没鬼) were responsible for their misfortune. Thus, they determined the best way to ward off the Demons of Sinking was to name each ship poop, thereby embodying the spirit of the floater into each of their creations. Because the Demons of Sinking are not only stupid, but also well known to despise foul smells, it was also believed this would trick the demons into thinking that Japanese ships were, in fact, sh*t. Japanese shipbuilding skill coincidentally increased markedly, and one, perhaps two, ships actually made it to the Korean peninsula (and back), where they learned that the term for government office was maru. Because the corresponding term in Japanese, kancho (官庁), has the same sound as both the Japanese name for ship's captain (艦長) and the common practice of samurai children (who are typically nicknamed maru) to stick their fingers in places they really shouldn't, this ultimately resulted in the proclamation in the year 1900 that all ships, henceforth, be called poop, when at all possible. This explains the modern term for bedpan, omaru (御虎子), and the Japanese fascination, in general, with poop.
More seriously, I found eleven distinct explanations that I grouped into four categories: ship personification, ship structure, shipping/invasion, and superstition. Below is a brief explanation of each theory. According to many explanations, maru is derived from maro.
Personification of prized personal possessions (愛称/人格/幼名)
In the Heian Era, "maro" (麻呂 or 麿) was used to refer to oneself, like "watashi" (私). According to many explanations, maro was eventually changed to maru. Prized possessions, such as a beloved dog, one's sword, etc., were often personified with maru. In addition, childhood names of samurai were often also suffixed with maru, such as Toyotomi Hideyoshi (豐臣 秀吉), who was known as Hiyoshi-maru (日吉丸) as a child.
This explanation stems from a similarity in structure with castles. The inner and outer citadels were referred to a hon-maru (本丸) and ni-no-maru (二の丸).
Something with a spherical shape is unlikely to sink (assuming it's hollow), so this explanation maintains that maru was used to ward off sinking.
Ships were typically constructed from timber sill in "log form" (There has to be a better translation of 丸太), hence the maru suffix.
Toi-maru is the name of what would probably best be translated as wholesalers, but the word seems to have a wider meaning. In modern Japanese, wholesalers are toi-ya or ton-ya/don-ya (問屋). Obviously, wholesalers are connected with shipping.
Toyotomi Hideyoshi renamed the Kishuku-maru (鬼宿丸) to Nippon-maru and invaded the Korean peninsula in 1592. It is said that this popularized maru in ship naming. However, the Bando-maru (坂東丸) from the Heian Era is the first ship known to have used this type of name.
Apparently the word for government office (役所 or 官庁) in Korean is/was "maro" or perhaps "maru", which is where the maru ending comes from.
Omaru is the word for bedpan or child's potty. To ward off evil spirits, maru was appended to children's names, as well as prized possessions. Several explanations also claim that maro meant poop.
According to Chinese legend, the diety Hakudo-maru descended to Earth and taught Emperor Huangdi (黄帝) to build ships. Ships are named with maru in tribute.
This made me lol and is clearly a joke.
丸は幸運のキーワード。船だと大漁、他だと商売繁盛、人気アップ、成績アップなどがあります。 ゴルフの丸山、巨人のマルティネス、モーニング娘（？）。などがその例です。 なお、副作用としてモー娘。の安倍なつみのように丸々と太ってくるといった現象も起きます。ダイエットが必要です。Circles (丸 ◯)
I actually found one explanation in Japanese about the safe return of a ship, but the person who wrote it doesn't seem to think it is true.