Thinking about most of medieval times the population was kind of too small to patrol and defend all of the coastlines. If one wanted to land somewhere else, provided it was not a tiny island, he would be able to, if he had the ships.
I'd recommend traveling to cost gold (something like the crusades, hiring ships to move your army), and the more defended the region is the more expensive the cost to disembark (as the captains would have to be extra careful on where to land, taking more risks).
Outright blocking disembarking should be expensive and impossible most of the times. That is why the Viking and Moorish incursions where so feared: there was little they could do to prevent them from disembarking, sacking and leaving. Too much land to defend.
Perhaps there could be a small sea-region bordering the coastline which would be permanently seen by the owners of the coast regions. Beyond that there's the mysterious ocean and there would be no way to scout. This would make disembarking a two-turn move.
Not all ships can dock everywhere. Not all shores are good for landing. An amphibious attack, back then, was much harder than what can be accomplished today.
