Pestilence is commonly found around the Tall Trees, Aurora Basin, and Tanner's Ranch area.
Try exploring the path south of Tanner's Ranch that runs along the river. Pestilence is usually around there.
War can often be found around Benedict Point, Tumbleweed, Gaptooth Breach and even just south east of Coot's Chapel. This horse can set zombies on fire by running into them.
Famine can be found around Mexico. Try searching the area just northwest of Torquemada
Death is the final horse of the apocalypse. You will awarded Death automatically upon finishing the story.