I've been kind of avoiding the question, because from what I remember in grad school the High and Late Middle Ages span from roughly 1001-1500, so that's a big chunk of time. (And I'm sure one of our medievalists will correct me on that if I'm wrong! Please don't be mean!)

Also, what i know about naval warfare is mostly from northwest Europe, so I can't really speak to the Mediterranean (let alone the Indian Ocean, Persian Gulf, Red Sea, the entire Pacific, the Indonesian archipelago, China, Japan ... etc).

But, with that out of the way: We have some pretty interesting depictions of ships from around the time of the Norman Conquest of England (1066 and all that). Here are some examples of William's ships, from the Bayeux Tapestry:

This one, if the site I found it on is correct on the Latin, is an English ship bearing news that Harold refused to give up the crown to William.(Harold's on the left, isn't he cute?) This is probably a fair depiction of a longship of the era, although we tend to think the sails were square and not triangular and the men are a bit out of scale to the ship per se. The crewman carrying the anchor aboard is a nice touch.

A little later on the tapestry we see shipbuilders preparing for the invasion and dragging ships to the sea. Note the tholes (holes for oars) and the bestial head on one of the ships.

And here's one of mounted knights getting on board the ship to take their mounts to England (look how crammed in they all are, and note the steersman at the aft end of the ship). When they got to England, they had to unload the horses, of course, which they likely did by tipping the ship by using the mast as a lever.

Now, unfortunately, that doesn't tell us a lot about those ships in combat, because William's fleet was unopposed. We also don't think that longships were used as actual combat ships very often, but mostly to land warriors. Any fighting at distance would have to be done with arrows or throwing implements, and boarding would be tricky because both sides could stave off with oars.

Combat between ship would have likely started happening more often once ship types were maneuverable with sails, and in fact we see ships in the 12th-14th centuries being equipped with elaborate offensive and defensive structures, called "castles."

Cogs were used widely in northern Europe to replace longship/knarr types of vessels, especially for trading. (The reasons why basically boil down to the hull type, greater space for cargo, more efficient sail propulsion and above all cheaper manufacture due to using what's called carvel building.) Anyhow, cogs had those high bow and stern area, called "castles," that could be used when ships came together to fight hand-to-hand. (I realize I said cogs are cargo ships, and that they were, but most "navies" of the period were gathered via a levy system, in the same way that armies would be mass levies of a king's retainers.)

After cogs (and concurrent with them), we see carracks, which were multi-masted ships with a large forecastle and after castle. They were larger than cogs and carried more men, and carracks are where we begin to see artillery mounted on ships. The Mary Rose is quite a famous carrack (although in my opinion it's a bit of a transitional ship, tending towards a galleon). The Mary Rose was one of several large ships built for King Henry VIII, including the Henry Grace a Dieu -- you can see the large castles and plenty of artillery there. The Mary Rose is probably most famous for sinking very suddenly in the Solent in 1545, with a full complement of sailors and over 100 longbowmen aboard, which tells us that it was used not only for its artillery but also for fighting among soldiers.

I think that's about all I have time for tonight, but please ask follow-up questions!

If I may piggyback on this excellent question, what was the purpose of the protruding spar on Late Medieval galleys, such as on [this example] (http://shipmodeling.net/photopost/data/614/ram1.jpg) from Venice? Were they used as rams, or for other purposes, such as a ramp for boarding?

EDIT: Additional image of full galley: https://www.modelshipmaster.com/products/ancient/argo/venetian%20galley%20(3).JPG

I wrote a bit on a related subject here.

To more directly answer your question, naval warfare developed quite a bit, in different parts of Europe, so I give a few illustrations here.

Spain in the Mediterranean

Spain's naval prowess evolved in nature over a rather long period in the development of naval power, and the development of the states that could afford to be a strong naval power.

Spain rose in strength (or more precisely the union of Castile & Leon, and Aragon, and Navarra) under Isabella and Ferdinand, at a time when Castile was the dominant power. In this period, Castile's major trading partners were the Nederlanders and the Italians. The discovery of the Americas and division of the world between Spain and Portugal meant that Spain had a new focus on the Atlantic, administered under the Council of Castile.

Following the reconquesta, expansion into North Africa also made sense due to growing need to import food items into Iberia, as Castile was increasingly focused on sheep-herding at the cost of agriculture. Under Charles V we saw a partnership with Genoa's galley navy in the region, where Genoa provided much of the naval assets and Spain provided the infantry to fight on the galleys and maintain garrisons (presidio) in the ports and towns they control.

In this period, the east coast (Mediterranean) of Spain, namely lands under Aragon, were in either upheaval or economic distress. So Spain's partnership with Genoa increased along with its strategic interest in the Mediterranean.

As Ottoman power in the Mediterranean grew, so did conflict with Spain and her allies. As we know, this culminated in the great Battle of Lepanto in 1571, where Spain's Philip II funded a large navy with Genoa, Venice, Papal State as partners. That victory was due to strong galley fleet that could maneuver under manpower even in the absence of favorable wind, carrying a large number of soldiers on board. The prevailing tactic was to fire once at close range as the galleys came close, then grapple, then send fearsome Spanish soldiers for boarding action. In fact, this is the instruction given to Spanish soldiers. Those who assisted with manning the guns were told to move to the upper deck after they fire the gun. The guns themselves are on older 2-wheel carriages, so reloading them was arduous if not upright impossible during combat.

The Battle of Lepanto itself was won through maneuvering and boarding action. The Ottoman flagship of Uluç Ali, the Sultana, was boarded by no more than 3 Spanish galleys. Seven Ottoman galleys came from behind the Sultana and their soldiers came on board the Sultana to fight the Spanish. The Spanish commander de Bazan's own galley joined the melée along with a squadron of Spanish ships, turning the Sultana to a battlefield into which soldiers from both sides poured in to fight. In the end, Uluç Ali was killed and his head was displayed from a pike, crushing Ottoman morale.

English gunnery

As war with England loomed, you have keep in mind several factors:

• Henry VIII Tudor was allied with Charles V of Spain, and his first wife was Catherine of Aragon, sister of Charles V. Henry had wanted to marry his first daughter Mary to Charles V, although Charles married a Portuguese bride with larger dowry. Instead, Mary was married to Philip II of Spain. This was part of Charles V's grand strategy of a northern orbit: Spain - England - Low Countries.

• The period of Mary's rule of England saw Spanish naval knowledge being absorbed by English shipbuilders. Mary ordered the building of race-built galleons following Spanish design but with emphasis on gunnery. This includes more guns and better reloading mechanisms, in particular re-design of the gun carriages to use 4 wheels. So basically while the vessels were designed in Spanish style, the armament was done in English style.

• Elizabeth, as we know now, was a Protestant and eventually led England away from Spain's orbit to become an outright adversary. She ordered further ships built following the design done in the era of Mary. These are the ships that led the battle against the Spanish Armada in 1588.

Speaking of which, the Spanish came into that battle first of all wanting to avoid confrontation with the English fleet. Their objective was to escort a large flotilla of transport vessels to the Low Countries where they could take the Army of Flanders across the strait to England, to conquer England. And this they nearly succeeded in doing, except for weather, English gunnery, and English persistence.

The two navies had very different goals. The Spanish would have much preferred to avoid the English navy. But they had to stay together as a fleet to protect the slow and vulnerable transports. If they had to fight, they preferred to fight on the decks, not from a distance. The English wanted to stop the invasion. They didn't want to fight a boarding action, they preferred ranged gunnery action.

The Mediterranean had taught the Spanish how to fight as a navy, culminating in their victory in Lepanto. But that style of fighting failed in the battle against England due to asymmetric objectives, advances in gunnery, differences between Mediterranean and Channel conditions, poor high-level strategy (most agree that the Spanish will likely have done better if they had either invaded England or Ireland straight from Spain itself, or have the Army of Flanders do their own crossing, rather than have to escort transporters literally around England first), weather, tactics, etc.

Other theaters of operation

I skipped over the Baltics, and various French attempts at building a navy, and of course the skirmishes between the Watergeuzens and the Dunkirkers. For those, I highly recommend perusing through the references below.

References

• Angus Konstam, "Sovereigns of the Sea," ISBN 978-0-470-11667-8, 2007.
• Geoffrey Parker, "The Grand Strategy of Philip II," ISBN 978-0300082739, 2000.
• Roger Crowley, "Empires of the Sea," ISBN 978-1-58836-733-4, 2008.