They came from the SEA?!

[Shovah32]

or you could hope that you find an icthyid province and mass them to go under.

[Nerfix]

Shovah32 said:
or you could hope that you find an illithid province and mass them to go under.

I thought that only the exceedingly rare magic site Crater allows you to get them?

[NTJedi]

Usually the fastest way to enter water provinces early in the game is buying mercenaries which can enter the water. Once you've conquered one water province it's easier to expand into the others.

If the Mercs are not available for purchase then it depends on your gem income.

[Teraswaerto]

The fastest and easiest way is to take an amphibious pretender like the Wyrm. It can start taking water provinces as soon as it can reach one, no items or magic needed.

[HoneyBadger]

One solution to consider as a partial fix is to recruit as many archers as possible in your shoreline provinces, since the water nations don't have much in the way of ranged attacks, and I don't think any missle troops-atleast in EA. It won't solve the problem, but it will give you an advantage, esp. if you can afford a commander casting fire arrows. Combining them with calvalry scripted to hold-attack should also help, particularly against EA Atlantians. Illithids are tougher, try mass-producing amulets of anti-magic and bows of botulf, and handing them out to cheap commanding officers. Shamblers on coasts seem to be common. I usually know where atleast one province with shamblers or ickthys are by mid-game. It takes a big investment of time and money though to really mass them, so if you find a province like that early in the game, grab it and hold on, and don't shirk on buying the troops each round, if you can help it. A hundred+ shamblers just sitting around collecting upkeep seems like a waste, but they're worth their weight in gold by the late-game. And ofcourse, who says you have to let them sit? There's no wrong time to invade the ocean, except when it's too late.

[Taqwus]

Regarding undead --

Skeletal types (longdead) and spectral types (ghosts) can.

Flesh/meat types (ghouls, wights, censors...) can't.

Constructs can also be amphibious -- ex. Mechanical Men are, if memory serves. Both constructs and undead generally have the benefit of poison immunity, which is quite useful there given the number of aquatic units with coral weapons or armor.

[Sir_Dr_D]

The easiest way to beat water nations is dominion them to death. There is usually not that many water provinces so it is easy to do.