From time to time you can get a hint in the tavern or from your spouse where to find a pirate hideout. They will never tell you the exact location but a region where you should search for the hideout.
Send one or two of your convoys to that region. After you spotted a pirate convoy, do not attack it, but follow it on its route. After some time it will head for the coast. In the moment the coast is reached, you have to be close to the convoy. Now the hideout should get uncovered.
Not every pirate convoy that reached the coast has to uncover a hideout, as they travel on relative static routes in the Caribbean sea, the coast can also be a turning point.
Do not use convoys with goods on board to hunt a pirate, he might attack you because of your goods.
After some time the hideouts will get uncovered by oneself, so you do not have to invest time to find them.