With patch 1.2 you nation reputation improves after you destroyed pirate convoys or pirate hideouts.

The amount of reputation gain is described here.

Annexing town will cause a hugh nation reputation drop. In case your reputation sinks below the threshold of 25%, you can not enter the towns of the affected nation and their military convoys will hunt your convoys.

For the worst case of 0% nation reputation, two pirate hideouts should be enough to increase your nation reputation over the threshold. Destroying the hideouts makes the biggest part of the reputation gain. As pirate convoys normally are normally anchored in the hideout, they deliver the remaining reputation percentages.