There isn't a load of science behind this but I tend to build "dream parties" for every AP I take interest in, so I might as well share.
Barbarian (consider focusing on the harpoon, it's versatile at range and good underwater)
Sorcerer (Elemental or Aquatic bloodlines are the most obvious, but Undead also has appeal if you want some of that zombie/voodoo pirate goodness)
Rogue (best choice for the wide range of skills that you'll need to be a good sailor)
Cleric of Gozreh (or Besmara, Calistria, Cayden, anyone chaotic)
Any race is fine, though I'd suggest going for the tengu because they fit the setting very well. I like the idea of making them all at least half-human and give everyone that "child of a famous pirate" trait to stack the Infamy boost, say they're all siblings.