Hi selan222,
Sorry about the delayed reply. Glad you're enjoying the game so far!
Duke is at the end of the bandit hideout (minecart dungeon) in a section only accessible after beating the water dungeon and unlocking Karena's sidequest. I assume you mean the ship itself? It's on the coast area west of Galadria after unlocking Elric's sidequest by beating the fire dungeon.
The story is definitely a weak point for me as I've not done the best job explaining things and the characters could do with some fleshing out. I might try and solve both with some minor character interactions to help with explain the story like you suggested.