How could Ramsay Bolton be taken by surprise by the Vale Army? They had taken the Moat Cailin, so I don't believe the Boltons knew nothing about the invasion from the south.
Why would Baelish need to fight through the famously impregnible Moat Cailin, when he could simply introduce himself at the gate and enjoy their hospitality? Much more his style.
Don't forget that everything Baelish is doing here - amassing an army and taking it North - is supported by a royal decree. He secured this from Cersei back when he told her about Ramsay marrying Sansa. Also don't forget, that as far as the Boltons were concerned, Baelish was an ally. He's the guy who gave them Sansa, which Roose noted was at great personal risk to himself.
He just needs to turn up, announce himself at the door, say that he's on royal business to bring his army to the Boltons, show that he has a royal decree with the royal seal, explain that it's for Lord Bolton's eyes only, and decline to go into much detail about what precisely that royal business is.
Whoever currently mans Moat Cailin would see an ally of their boss, on the business of their boss's boss, and would have no reason not to let them through. As Andrew Mattson's answer points out, he was camped at Moat Cailin. Most likely, he was enjoying their warm hospitality, drinking toasts to Lord Bolton at their high table.
He's very good at this sort of thing, is our Petyr...
Ramsay's reaction at their arrival was one of only slight surprise, followed by a look of dejection when they attack his side. My reading of it was that he was thinking "Oh, he's here early. Don't really need his army, we've got this one wrapped up already. I hope he doesn't expect me to pay... Oh... Huh. So that's why he's here. I should have seen that one coming. I guess I lost this game...".
Why did Sansa send Brienne to the Blackfish instead of a raven? Because a raven might get shot down or otherwise intercepted by Ramsey.
Does it not stand to reason that an army with overwhelming force, one that had been dormant during recent conflicts more central to their own sphere of influence, and one no one would think think had reason to get involved (Littlefinger gave up Sansa to marry Ramsey, and his influence over the feeble Lord Arryn might not be that well known outside the Vale), might be able to stage an attack on Moat Caelin where they'd cut off communications, surprise and overwhelm the ruined castle and then move on?
It's not like they had satellites or SnapChat.
EDIT: My speculation about that is actually pointless (S06E05):
Littlefinger: I rode north with Knights of the Vale to come to your aid. We are encamped at Moat Cailin even as we speak.
The Boltons may have taken Moat Cailin to free up Roose's army, but they clearly did not garrison it. Whether they pulled them back when Stannis marched on Winterfell, or they only cared about it because of the obstruction the Ironborn posed, the Knights of the Vale took it well before the battle.