The quest requires you to go everywhere, and fight dozens of everything on land and sea. (And search a whole lot of crates.) It's basically an A-Z of the entire game map. The best way to speed it up is joining a large active guild, so you can get around quickly by teleporting to people and ask them to look out for target ships. Having a full crew would also speed up the ship hunting parts, but that's causing a lot of crashes in the current version.
Oh yeah, and being good at poker couldn't hurt.