They came from the SEA?!

[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.