There are many motives for travel in the world of Crusade!, and people of all classes and nationalities travel extensively across the known world despite the difficulties. From the pilgrimages of the faithful to the icons and relics of the saints; to the diplomats and spies moving information; to the merchant who needs to import and export valuable goods; to massive armies transported by Kings and nobles to fight battles in far off lands; transport is key to everyone, and its difficulties are a large part of life.
Remember that without the Navigation skill traveling becomes dangerous, exhausting and complicated. Doing anything more than the shortest of journeys (going straight between one town and the next) in a turn will give you penalties to your skills and actions on arrival. Those traveling to the yearly meetings of the Covenant can be expected to arrive without much hassle as it is very easy to find others to travel with.
The fastest and most typical method of land travel in the 12th century is the horse. Whilst they are simple in terms of technology, they themselves pose many problems. Horses require feeding and stabling (itself potentially costly), and need to be transported over any large body of water. Their speed is limited - at the absolute most (given ideal circumstances, including at least one change of well-bred horses at points during the route) nearly seventy miles in a night; though normally might only cover thirty miles in a day, and if needing to bring large amounts of supplies and other paraphernalia down to fifteen or twenty. Often mules are used to pull wagons and the like for longer distances, and for very short journeys a trip on foot is more common.
Land travel is complicated by the lack of decent roads. The Roman system of roads has for the most part collapsed and been replaced by muddy paths that are pot-holed, rutted and worse, especially in winter. Bridges too are often poorly maintained, and frequently there are few usable bridges outside of towns which have grown up around them. Wagons are primarily the province of the very poor or sick, with others favouring the saddle horse, due to uneven road conditions making travel very uncomfortable.
It is only at sea that reasonable time can be made with large quantities of goods. By the 12th Century, technology includes the rudder and the compass, and shipbuilding is improving to the point where ships are wide, spacious, and safe. Single-sailed Cogs are the norm and can with a skilled captain and crew travel relatively fast, up to speeds of twelve miles per hour with a favourable wind.
Traveling the Middle East is a dangerous task. Universally harsh terrain (for any Western Crusader that is), mixed with barren hills, verdant woods, and worst of all, uninhabitable deserts. The perfect form of travel for the middle east is by large Caravan, concentrating your army and supplies into columns in order to prepare for hazardous terrain and surprise attacks.
Horses are useful, but tire far too easily where a Camel would prevail - stubborn yet hardy beasts, many traders make city-size fortunes off the breeding and selling of Camels.
A (possibly native) guide to these lands would be more than helpful - a General would be mad to venture his army into the Arabian Desert without a Bedhouin escort, or a Seljuk for the mountains, or an Ayubid for Africa.
Being a soldier is hard. It mostly requires long, long exhausting treks across both desert and ocean, with a good chance of dying from exhaustion, disease, drowning, sunstroke, thirst or any of the savage and untameable creatures that inhabit the world. As a commander of men, it is your duty to make sure the journey for you and your army is as safe as it can be. Whether this is by purchasing exemplary ships or caravans, not annoying the locals whose countries you trample in the process (especially the Byzantines), investing in magic, superior food sources or praying (obviously).
An army marches on its stomach. A cliché, but incredibly true. You cannot field a sizable army without securing some amount of food. This can come from razing the nearby lands and stealing food from farmers and peasants (probably what your men might do if left to their own devices), to arranging supply trains and caravans to bring food to your men - a task fraught with administrative difficulties. In certain areas (primarily the desert, of course) water is also going to be an issue. The relentless heat of the Levant will not only cause Crusading knights to bake in their helms, but will make finding water all the more crucial.
Further, armies are slow. Slooooooooow. You can't expect a whole army to march on foot across Europe any time soon. You need to arrange them transport, and even then they aren't going to be moving quickly, what with supply and baggage trains, stopping to camp every few seconds, and the general milling around of the untrained peasant rabble. Ships are essential for longer journeys since they can move lots of men and loads with ease, but are likely to be expensive.
Armies will typically require most of a season to traverse medium distances. As each turn in Crusade! is one year long, this usually means that your army can reasonably travel and give battle within the one year. Longer distances (such as traveling from the Western Kingdoms or the Lands of the Rus) may take longer and could take all year to reach a specific destination in the Levant.