A battle in 4e is probably best treated as a mix of combat and roleplaying and/or skill challlenges. Normal combat for those times when the PCs are in the thick of the fight, face-to-face with enemies. Roleplaying or skill challenges for things like strategic insights, tactical advantage, rallying your own side's forces and demoralising the enemy.
As Korgoth says, you wouldn't want it to be one long combat lasting dozens of rounds, that doesn't work. Instead there should be multiple combats of typical length with short rests in between. I understand that this is actually quite realistic for fighting in plate armour. The wearer would get overheated after a few minutes and have to retire.
That's pretty similar to what is suggested in
Heroes of Battle, iirc. Depending on how the PC group does in a series of encounters, the battle may be won or lost, or more casualties will be suffered, or some advantage goes to their side if they succeed. It doesn't really cover PCs as commanders, but that's a rather different problem.
As for how a battle would go, I'd suggest that magic would lead to the use of wide and shallow formations. It's all very well launching a fireball at a formation but if that formation is only two or three ranks deep, you really aren't having much effect on a large army. That's normal for medieval armies to form up in shallow formations, and cavalry would often be in single ranks,
en haye being the technical term. Personally I'd expect more 'Turkish' style wave tactics rather than a charge, at least in the initial phase of a battle.
The other thing that I feel sure would develop is skirmishing. Even more so than shallow formations, low troop density makes casting spells less useful because the targets aren't available. Lightly-armoured spellcasters seem like a good choice of target for troops armed with crossbows, bows, or even javelins. And without the resources available to 3e wizards et al they aren't as capable of protecting themselves fully.
One other idea, which partly comes from a novel I don't remember the name of. Military units often have standards, battle songs, rituals, etc. In a world where magic works, these rituals might actually be magical. Before a battle units get together, a unit 'priest' who has never cast a spell in his life but who knows the ritual (Ritual Magic feat) directs them in chanting their battle prayers, pours sacred oils on the standard, promises part of the booty to the unit shrine where the standard rests, swears in the group of elite soldiers who will protect the standard or die trying, and by doing this establishes some sort of protection for the unit. Whether it's a morale bonus to attacks, some sort of magical protection against fire, enhanced mobility, or something else might vary from unit to unit or even according to the particular ritual performed, but it should give something back. Maybe standards that have been used many times before for this give greater effects and famous old units are better protected magically, but that would be something for particular GMs to decide. But in 4e it seems like a very practical use for Ritual Magic.
