Its different in MTW. In order to move men around you need 3 things. Sea superiority is crucial for this and takes awhile to achive.
1. a port in the province the army resides in
2. ships all the way to your desired destination with at least 1 ship in each ocean area.
3. unblockaded sea tiles, so crucial is this I divide it from above. If there is one enemy ship in the way you can't move men through and also can't trade.

For example, as the danes, in order to invade northumbria from denmark you need ships in that little scandanavian sea where the denmarkian port is and also one or more ships in the north sea. If the english have one boat in either spot you can't invade. Even if you are neutral to the English at the time you invade they won't let you through. If you have sea superiority you can drag the your army from denmark and plop it down in northumbria.

For you in invade the middle east you'll need an unbroken chain of ships all the way from France or where-ever your army is to which ever territory you wish to occupy and no hostile ships can be in your way. Remember, you can't invade a neutral province if they have ships in the water as well. Your quickest bet might be a crusade but you can do it if you build up sea superiority.

Welcome to MTW by the way :D I hope that clears it up, if not post any problems.