Pony Express missions are found in both Dodge and Empire. In Dodge it's the "Earl - Pony Express". In Empire it's the "Daryl - Pony Express". They are unlocked as you move through the game. I really recommend doing them as soon as they're unlocked, to build up your stats and earn money. It's also great to learn the map well, so you know the fastest ways to get places.

#1 - Tiny Tubbs / Dodge
You're told to lend Tiny Tubbs a hand. Run down to the X, as Tubbs is standing by a horse. Stand by the horse and then talk to Tubbs. He's staaarving!! You'll have a timer and have to get down and up the street before it expires. Jump on your horse and run to the storekeeper at the other end of the street. Jump off, talk to him and get a new timer. Now leap on your horse and race back to Tubbs. Leap off and talk quickly to end the mission.
+5 horse, $10 cash

These next ones unlock in Empire after the Hoodoo mission.

#2 - Johnny / Empire
Daryl says to talk to Johnny. Johnny appears as a new person on the map at this point. He has horse with a bad shoe. You have to ride this horse super fast to stable. Does this make no sense to anybody?? In any case, race the horse straight back and then sideways to get there.
+5 horse, $10 cash.

#3 - Stumpy / Empire
Stumpy is at the hardware shop. Go over to the X to talk to him. He says to take supplies to the rail workers. hop and run quickly. across the bridge north. you get shot at as you ride. take the narrow alley in the rocks to get there in time. it's close! "We can step up the pace now - If I can keep teh irish sober" +5 $10 alternately a tthe bridge you can go right, down the railroad path through the tunnel and straight to them.

Gun Walkthrough