What affects party speed:
Your riding skill affects your individual speed. (athletics if you're not on horse)
Type of horse DOES NOT affect your speed.
You need a lot of mounted troops in your party to have a noticeable speed increase.
If your army is mostly infantry, having a bunch of mounted prisoners will speed you up.
Speed depends on how much stuff you are carrying along, - extra horses will decrease this penalty, but won't raise your total speed.
Finally, pathfinding increases your overall speed by a bit.