From the Super Mario Wiki
At the start of the episode, the Gondolier arrives in Desert Land via a warp pipe, and lands in front of Mario and his friends. He explains to them that everyone was fleeing Venice because it was under attack by a sea monster. Mario, feeling an unexplainable attachment to Venice, recruits Luigi, and the bros. head off to deal with the monster, which turns out to be the Doomsub.
After Mario and Luigi stop Bowser and Kootie Pie from taking over Venice, the Gondolier takes the heroes for a gondola ride. He stops in front of two statues Mario and Luigi passed earlier, and explains that they were Marco Polo's Plumbers, whom the brothers almost identically resemble.