I need to get that horse! Some wikis said that the horse hade a fire mane and was hard to find but tell me the location of War, the horse.
There are four mythic horses in "Undead Nightmare", rather than one. You asked about War specifically, but I'll include info on all four.
When the horse spawns, you'll see a message that says something along the lines of "A mythical creature is nearby!". When you see that message, look around and get ready to tame the horse. None of them are incredibly difficult to tame.
Aside from having way more stamina than normal horses, each mythic horse has special abilites: