After you defeat King Calamari and make your way through the rest of the Sunken Ship, you face off with Johnathan Jones.
First defeat the Bandana Blues. If you have a multiple-target attack, such as Mallow's Thunderbolt, use it. Johnny and the Bandana Blues will use regular attacks with spears, and the Bandana Blues can also use a stronger attack called Pierce.
Johnny can hit a single character with Diamond Saw. Johnny can attack with Skewer, which does low damage and can be blocked if you press the button after the chain has fully extended. Johnny's normal attack can be blocked if you press the button just before the chain extends. Johnny can attack with Mega Drain, which restores some of his HP.
Eventually Johnny will use the move "Get Tough!" and turn red.
After a while, Johnny will challenge Mario to a one-on-one battle. Your companions, and Johnny's Bandana Blues, will watch the fight and you won't be able to control your allies.
Mario's Special attacks are not very effective on Johnny, so just use regular attacks.
After you defeat Johnny, you get a Star Piece.
Go to the east side of the room and go through the door in the northeast wall, then jump on the spring to go outside.
Return to Seaside Town
Go back to Seaside Town and there will be a cutscene. You have to hand over the star or you won't be able to proceed, so do it. Afterward, if you need supplies, you'll need to go east to Marrymore or somewhere else with a shop, because the Seaside Town shops are empty now.
When you're ready, go back to Seaside Town. Go northwest and use the northwest exit of town to find Yaridovich and his cronies. After a cutscene, you have to battle Yaridovich.