Once the reputation reaches the maximum for that Notoriety level, the pirate's Notoriety increases and a new maximum is set, that is until you reach level 50 or become a mastered pirate.
The amount of reputation may be a set value, like completing part of a quest or an entire quest. But, reputation earned from defeating enemies or sinking ships is relative to the Skills of the pirate vs. the level of their enemy.
There are occasions where you can get special potions and quests to increase the Notoriety your earn. Another way to boost you Notoriety is by being in a crew.
Note: Level 50 pirates do not have a maximum set of reputation to earn, for they are mastered pirates.