It is interesting to note that horses have never been shown or mentioned in a Fallout game, other than in the rantings of Dane in Fallout, Paulson and Sally in Mothership Zeta, and President John Henry Eden in an Enclave Radio broadcast. This indicates that horses did not survive the Great War in North America, although there is a possibility that they exist in other parts of the globe.
In All Roads, the graphic novel, every NCR soldier seen in Chance's flashback of the Bitter Springs Massacre are riding horses. Given the number of continuity errors between All Roads and Fallout: New Vegas it's likely this is merely another such occurrence.
A "Horse Marker" can be found in In the G.E.C.K. (editor).
When asked about the horses seen in All Roads, Chris Avellone said, "To me, that picture in the comic was an error (no one noticed it until too late) and that "it was never my intention that there were any horses." He went on to say that "there were parts of the New Vegas design where we specifically removed the mention of horses from certain narrative points (one of Raul’s stories originally referenced horses, for example, and we cut them because we didn’t want to imply horses still existed)."