Alright, Takhisis asked about how fleets work, so I'll explain it here for everyone:
As you can see, the seas is divided into regions I will call sea tiles. When you recruit a fleet (in the same way as you would recruit an army), you choose which sea tile your fleet is based in. A fleet can be based and can only move in sea tiles which is next to provinces either you or your allies own. So, if you are, say, Egypt, you can't simply move a fleet into the North Sea (Oceanus Germanicus) unless you or an ally has a coastal province bordering the sea. All fleets move at a leisurely pace of 1 tile per turn.
Unlike armies, navies are stackable, and you can, theoretically, have an infinite number of fleets in a sea tile. You can share a sea tile with fleets from friendly or neutral countries. When there are hostile fleets in the sea tile a naval battle will ensue.
Naval battles are calculated the same way as land battles, with the difference that the base strength of your navies (ie the strength before any RNG or modifiers are added) depends on the
Navy Quality value instead of the Army Quality value. You gain this the same way as you would gain Army Quality - by gold investment.
The main role of navies is to keep the seas safe for amphibious landings. All armies can perform amphibious landings but will suffer a -25% penalty unless they have the "amphibious" trait. This is how it works: armies can move through any number of sea tiles at any time to get to a province with no extra movement cost unless there's an enemy fleet in that sea tile.
Say the Roman army in Campania wants to invade Carthaginian Sicily.
The Roman army has two paths to get to Sicily. The first is blocked by the presence of five Carthaginian fleets, but there are no enemy fleets in the second and the army can pass through this. However, if in the same turn the other Carthaginian fleet to the south moves into that sea tile, the transports will be intercepted and the army will be destroyed. To be safe, you'd want your own fleets to be controlling the sea tile your army is crossing.
The number of sea tiles the army must move through doesn't matter but the same restrictions that apply to fleets also apply to army transports - armies can only move through sea tiles which is next to provinces either you or your allies own. So this Roman army in Italy can't just move via sea and attack, say, Denmark unless they or their allies control provinces bordering either the North Sea or the Baltic Sea.