Ship-king was a title of dubious formality which applied to any one of these four successive Kings of Gondor:
The title referred to the main preoccupation of their bearers: the rapid expansion of the Gondorian navy. From TA 830 to TA 1149, these kings worked hard at, and were largely successful at, adding territory to Gondor with their increasingly superior naval might. The Ship-kings pushed the boundaries of Gondor to the south and to the west, such that Gondor came to include land down to the Mouths of Anduin and Umbar and even south of the River Harnen. Indeed, it was under the Ship-kings that Gondor achieved the zenith of its influence, at least until the coming of Aragorn and the Reunited Kingdom.
Falastur began the building of great fleets of ships that increased Gondor's power in Middle-earth down past the Mouths of Anduin. Eärnil I rebuilt the ancient haven of the Faithful Pelargir and from here built a great fleet to conquer the enemy realm of Umbar. In TA 933, Eärnil's navy and armies attacked Umbar and won it from the Southrons and their Black Númenórean masters. Afterwards, it became an important part of Gondor, serving as a great harbor and fortress of Gondor. During Hyarmendacil I's time, the Kingdom of Gondor reached its highest peak and the realm extended from the Field of Celebrant, to the borders of Mirkwood, to the west of the Greyflood, just east of the Sea of Rhûn, south of the river Harnen, and finally to the coastal province of Umbar.
The Ship-kings ushered in a 'Golden Age' bringing Gondor great power and wealth. At this time, the Men from the Vales of Anduin and those of the south acknowledged its authority and did homage to it. Mordor was well watched and the fortresses built to watch over it were well-manned and maintained and it remained desolate and unpeopled. The line of Ship-kings ended with the death Hyarmendacil I leaving behind a great empire that his son Atanatar II and subsequent later successors, did little to maintain.