Except for the Norse, it is almost a topic I almost never hear about. I am especially curious about outside of the Mediterranean, as I find it difficult to believe that the British Isles had no serious mariner tradition.
Naval combat, although not as common as land-based warfare, definitely did happen in medieval Europe, both in the strict sense of ship-to-ship engagements as well as the involvement of naval elements in amphibious operations. You are also correct in assuming that there was a mariner tradition present on the British Isles; in the Kingdom of England in particular. Or at least it had a strong enough mariner tradition to substantiate a naval doctrine.
One of the most comprehensive sources we have on naval combat in feudal Europe is the Black Book of the Admiralty, an English (albeit written in Old French and Latin) naval treatise from circa 1360 that contains rules, regulations and guidelines for admirals and their subordinates where it concerns their conduct on sea and on land. as well as more practical matters such as wages for the sailors as well as reimbursements in case of ship loss. Arguably the most relevant chapter in relation to your question is the chapter translated by Sir Twiss as Instructions what the Lord Admiral is to doe, at sea and land in tyme of warr. It contains 20 items, of which I will list a few, such as item VI, detailing what to do when an enemy ship is sighted:
*Item en cas que aucune nef ou autre vessel de la flotte apperceyue aucun vessel ennemy sur la mer doncques il mettra une banere en hault par laquelle la nef de ladmiral et autres nefz de la flotte pourront avoir congnoissance qu'il a veu ung vessel ennemy ou plusieurs et ainsi apres ordonner le mieulx quilz sauront pour lencontrer.*^(1)
Item in case any shipp or other vessell of the ffleet perceive any enemies vessell upon the sea, then he shall putt a flagg aloft, by which the admiralls shipp and the other shipps of the ffleete may know that hee hath seene one or more of the enemies vessells, and soe to contrive the best they can to meet therewith.^(2)
Another item hinting at naval combat is item VIII, dictating what to do in time of resistance:
*Item se aucunes de noz nefs on vesseaulx encontrent sur la mer ou en ports aucunes autres vesseaulx qui facent rebelletees ou defense encontre ceulx de noz nefs ou vasseaulx adoncques bien lise a noz gentz les autres comme ennemys assaillir et par forte mayn les prendre et amener entierement comme ily les ont gaignez devant ladmiral, sans eulx piller ou endommager illecques de prendre ce que loy et coustume de mer veult et demande.*^(3)
Item, if any of our shipps or vessells doe meete upon the sea or in ports any other vessels which doe make any resistance or defence against those of our shipps or vessells, then it is lawfull for our men to assaile the others as enemies, and by force to seize and bring them before the admirall entirely as they have taken them without pillageing or indammageing them, and there to receive what the law and customs of the sea wills and requires.^(4)
The presence of a treatise on naval doctrine illustrates that naval combat wasn't considered a rarity or anomaly, at least not by the second half of the 14th century, but that it was part of the military thought of the time.
We also know of naval combat in other locales within feudal Europe, from narrative sources as well as receipts and accounts. I have written about the naval origin of the approximate of the levy system in the western Netherlands before, but from other events we know that the naval component of warfare in that region was not limited to such. One naval encounter with an extensive historiography is the 1304 battle of Zierikzee, which lasted two days. The Franco-Hollandic fleet was commanded by Admiral Grimaldi, a native of Monaco and a veteran of the Sicilian Vespers^(5), they fought a Flemish-Zeelandic fleet under the command of Gwijde (Guy) van Namen^(6). The Franco-Dutch fleet numbered 55 ships, a mix of galleys and cogs^(7), and the Flemish-Zeelandic fleet numbered roughly 70 ships^(8). The sources tell us of everything we would expect from a naval encounter, recounting the use of fireships, (cross)bows, as well as ship-mounted oestrellen and springaelen, akin to massive crossbows, to be followed by a phase of boarding and fighting from deck to deck^(9). The respective fleets had been formed up in several lines, and the commanders were attempting to maneuver in such a way to get the sun behind them, tactics that suggests that naval battles at this point in time were far from haphazard affairs that had no precedent^(10).
Albeit that Grimaldi was native to the Mediterranean, it is safe to conclude that naval combat was a well developed and thought out affair in other areas of coastal Europe by the beginning of the 14th century at the latest.
EDIT: Tried fixing the quotation format. To no avail.
EDIT 2: Interestingly enough (for me), this is marked by Reddit algorithm as one of my most controversial comments. As such, if anyone does have critique, I invite them to comment; I am very much open to criticism and might learn something, even if I'm confident in my sources and drawn conclusions.
To build on /u/Goiyon's excellent answer, ninth and tenth century England definitely had a strong maritime tradition. Alfred of Wessex is often credited with the foundation of the first Royal Navy in response to the Viking threat. We do know that he led several successful naval actions against Danish fleets that were threatening the English coast, although naval actions do appear to have consisted largely of boarding enemy boats and fighting as on land. Surviving Anglo-Saxon royal and episcopal wills do show bequests to pay for armour and weapons for some English ship crews, which likely would have given those men a definite edge in tight, shipboard conflict, albeit at a risk of drowning. The English navy certainly saw extensive investment during the reign of Edgar the Peaceful in the 970s as well.