I think the first thing to bear in mind that even it we had navies, we probably wouldn't see any ships larger or more advanced than triremes given the era.
Obviously it's far too complicated to be implemented any time soon, but I think I've come up with a way it could possibly work.
If you look at games such as Rome Total War, they have a similar basic concept to BM e.g. mostly focused on land battles and administration of realms. When it came to naval elements they had to include something but a full naval combat system was far too much complexity for them to handle.
Instead, they created large numbers of trade routes which could be blockaded by navies.
So here's my suggestion, and again, this would be for the distant future.
How about if a lot more sea routes were created on the maps? These could go between all cities townslands on the map and should probably include making some rivers navigable. Each of these routes should then have set points on them at semi-regular intervals for simplicity.
You could then give the realms an option of spending money to build ships (similar to building fortifications or other infrastructure). However, these new units could only be given specific missions. So, for example, you could order a ship to sail to a particular point on a route and blockade it. This would mean that only traders or units from appropriately allied realms could use the section of the trade route that is being blockaded.
These ships could then remain there and continue blockading it until they either reach 80% damage and sail home to repair (the repair process could be similar to repairing fortifications) or are engaged by another fleet that they meet at that location. If two fleets meet you could use a similar combat engine to now and then whichever fleet survives continues with its mission.
This would add something of a naval flavour by restricting the ability of people to travel across the water and would give a new, albeit limited, scope to conflict.
Obviously something like this would take a long time to implement as, amongst other things, it would mean drawing new routes on all the maps.
Oh, and one other thing. Another reason for using points on the routes is that it gives the game a way to work out how long the fleet should take to arrive at that location and if each one was given a name it would then enable people to name the battles e.g. the Battle of Cape Saffalore, etc.
