Coincidentally, I'm playing Skulls and Shackles right now with my first Witch. It's 25 point buy to boot. I haven't gotten the chance to play Pathfinder much before this and tend to focus on RP aspects as much as mechanical, so I can't be counted on for much optimization, but I've survived thus far with no troubles (albeit in a large party, so that helps).
The Witch is kind of flexible. From what I can tell, this class can do a number of things -- not all of them perfectly or optimally, but you have multiple workable options. It all depends on what you feel like playing and what bases your group needs covered. Personally, I think I'll be headed down the debuff/control route.
Stats:
I'm playing Catfolk, though, so my stats came out to this:
Str 11
Dex 14
Con 14
Int 16
Wis 10
Cha 12
Your Wis score isn't hurting you (I'd put mine higher if not for Catfolk's -2), but if you want to cut something to raise another stat, I'd cut there. It doesn't do anything special for Witch. The one thing I'd look at is whether you want to take Evolved Familiar down the line as Cha 13 is a prerequisite for that. Otherwise, I'd say you're looking good. I honestly can't remember why I put that point into Str... not very useful.
Hexes:
I started out with Fortune and Evil Eye myself. I would not really recommend Fortune as a starting hex -- it's never turned the tide of a battle, and again, I've moved more toward debuffs/control/etc. Fortune is potentially worth it if you do want to go the buff route, but it's best combined with Cackle. If I could redo it, I'd likely grab Slumber instead of Fortune. There have been a number of cases at first level where (especially before I got my hands on a crossbow) I just couldn't do much in battle, and Slumber would have helped immensely there.
Evil Eye is more useful with Cackle as well, but I've gotten some mileage out of it without because battles tend to go so quickly with my party. So I can definitely suggest Evil Eye (especially when you hit 3, as I am, and start to get decent control spells that allow the target to save).
Fly is also good, but I'm holding off until level 4, when I can actually use it to fly (before then you do get free Feather Fall which can come in handy for sure).
As far as Water Lung goes, I don't have it. We just finished the first book, and I've been in zero situations where I would have wanted it over other hex choices. However, every game is different, and it certainly won't hurt you to have it. I'll probably pick it up eventually.
The Healing hex might be useful if you don't have a healer in the group or find that you need more healing than the healer can provide, but the Witch is not the best healer out there. It's just something you can do if it's needed or it fits your concept.
Cauldron with Craft: Alchemy is viable if you wanna go that way. Again, it seems to be one of those things that the Witch isn't _the_ best at, but you can totally do it.
Feats:
Yeeeah, it's probably going to be a lot of Extra Hex. Hexes are your main trick. There are a few notable things I've considered, though. I might pick up an item creation feat; nobody else in my group really does that, and it could come in handy.
There's Evolved Familiar, but I don't currently have the Cha for that and will probably pass on it.
At level 7, I may take Improved Familiar, but before that it hasn't really been worth it to me (I want a Mephit, darn it). It's also contingent on whether my GM will let me keep all my spells. RAW is kind of unclear -- it really sounds like I'd have to dismiss or kill my current familiar to get the new one and, following the normal rules for a Witch's familiar's death, lose spells. Those Witch rules make perfect sense if your familiar gets killed in battle or in other circumstances, but it kind of sucks to lose my rather limited set of spells for an upgrade I'm spending a feat on.
Patrons and Archetypes:
Majorly depends on what direction you want to go. The one thing I wouldn't recommend is Sea Witch. It's cool, but it felt like I would lose more than I gained.
I'm using the Water patron just for flavor; I knew it wasn't going to be the greatest, but hey, it fit with the character (I chose a crab familiar for the same reason -- useless mechanically but so cool!). There are times in the future that it could be useful, but thus far it hasn't done much for me, and you can likely do better. Shadow could be nice, and of course Time will eventually net you Time Stop if your game goes into the 18th level. Trickery's 18th level spell is also Time Stop and could be useful. Really, just browse and see what pops out at you.
Spells:
This, again, will depend on what direction you want to go. If you're worried about squishiness, grab Mage Armor. Ear Piercing Scream, if allowed, has been occasionally useful. I haven't used it even once, but (again, if allowed) you might look into Air Bubble.
At level 3, if you want to do control, I'd recommend Glitterdust and Web. I took Web but skipped Glitterdust (for now) for Steal Breath, an ARG Catfolk spell.
Traits:
Heart of the Sea sounds great! Lucky human. :P
I took the campaign trait Touched By the Sea, but Heart of the Sea has that more than covered (so naturally choose something else if you get a campaign trait as well). We got one campaign trait and one normal trait, so I also got Reactionary because hey, Init never hurts.
To anybody playing Catfolk, Climber is a great trait for this campaign.
Skills:
Swim and Profession: Sailor are very handy for the entire party. Luckily, Profession is a class skill for Witch. Climb is useful too (though in my case, my Catfolk stuff has that covered). Think about what would help you on a ship. Other than those, I've probably used Spellcraft the most. Highly suggest you go for that. Knowledge skills never hurt you -- I've got Arcana and Nature. I can see Knowledge (Local) for the Shackles being a good choice too. And, of course, if you want to use the Fly hex, then Fly will come in handy.
