The correct solution is to use whatever the contextually correct form of emphasis is for the ship name. This depends on the format and the default styling. As the question points out, when the running body text is in Roman type, emphasis typically means using italic type. When the emphasized text is embedded inside something that is already italicized, the emphasis is indicated by reverting to Roman type. So, in most printed contexts, the correct notation for the title would be:
The Voyage of the Dawn Treader
with the ship name in Roman type.
For most situations, this should provide a satisfactory answer. However, there are cases where the correct indication of emphasis is something different. In handwritten or typewriter-produced texts, the standard for emphasis is to underline something. Multiple iterations of emphasis can be handled by multiple underlines. (Historically, this was something of a workaround, since it was difficult—when writing by hand—or impossible—using a typewriter—to produce reliably recognizable italic type, so a different procedure was needed. However, it developed into its own scheme with well-defined rules.) This is why HTML has separate tags for <i> (for italic) and <em> (for emphasis). The first denotes a typographical property, while the second denotes a semantic one. If the style sheet for a Web page called for the main body text to be italicized (as sometimes happens), then the <em> should be defined to switch to Roman type for emphasis.