How do you move in water or attack ?

[Foodstamp]

Jotunheim has some water magic. Research the conjuration tree a bit and you will get access to some amphibious summons.

Also, most undead are poor amphibians. So summoning the death magic conjurations will help you as well.

Since you are playing against the AI, all you need to do is blend this force with the units you have found in provinces along the shoreline such as the shamblers, and push for his capital.

Craft a few water breathing items to give to some of your better commanders to allow them atleast, and some of your troops as well if your construction is high enough, to enter the sea.

And to answer your question, yes they all need to be atleast poor amphibians.

Goodluck!

Edit: Bah what he said