Something I have never really seen discussed is the logistics of marching an army during this time period. I'm not bothered about the crusades as such but this seems a good example of an army having to march a long way.
On top of the marching how were things such as supply lines handled? Did they rely on tribute from other cities?
Marching such a long distance was a difficult endeavor in the medieval period, for precisely the logistical reasons you highlight in your question. As I just finished teaching a course on the Crusades, and since they provide the best/only examples of armies marching from Europe to the Levant in the medieval period, I'm going to focus on them.
Depending on your perspective, there were 8 "major" crusades (this is a loaded statement of course) called for and endorsed by the papacy, with the goal of reclaiming the Holy Land, comprised of European armies, with France, England, and the Holy Roman Empire supplying the bulk of the troops. Of these 8 crusades, the 1st, 2nd, 3rd, 5th, 6th, and 7th made it either to the Levant or Egypt (the 4th Crusade got sidetracked and sacked Constantinople, and the 8th Crusade targeted Tunis). Of these crusades, only in the 1st and 2nd (and part of the 3rd) do we see large armies marching en masse across Europe, with the remaining expeditions preferring the sea route, often stopping off in Cyprus before making landfall in Outremer.
The 1st Crusade was called (though it wasn't yet referred to as a "crusade") at the Council of Clermont on November 28, 1095, and forces were on the move by late summer 1096. Ignoring the "People's Crusade" or the "First Wave," which was slaughtered quickly in Asia Minor, the forces of the 1st crusade departed Europe as a series of smaller armies, led by well-known figures such as Godfrey of Bouillon, Raymond of Saint-Gilles, and Bohemond of Taranto, before combining their forces at Constantinople. These various contingents departed Europe in (roughly) August 1096, and arrived at Constantinople between November 1096 and April 1097. So, to get from one end of Europe to the other in the 11th century, it could take up to 9 months before you could stand on the edge of Asia. From there, the combined army began its tough slog across Asia Minor, eventually making it to Antioch in late October of 1097. Crusader progress slows considerably at this point due to sieges and infighting, but to answer your initial question: it would take somewhere in the neighborhood of 13+ months for an army to march from Western Europe to Syria. The 2nd crusade gives us a similar impression, with Louis VII's army leaving eastern France in June 1147 and making it to western Asia Minor by January 1148. The 2nd crusade fared much worse in Asia Minor than had the 1st, and so it becomes harder to track after early 1148. As for the 3rd crusade, only one of the 3 major contributors took the land route, and that army under Frederick Barbarossa went from Germany to central Asia Minor in a little over a year as well. So, roughly, you could expect to spend more than a year on the road to go from Western Europe to the Levant.
The remainder of your question, regarding logistics and supply, explains why so few of the crusades opted for the land route across Europe and Asia. Since antiquity all the way through to today, transport via water has been less expensive than transport by land, and so whenever it was feasible we see crusade leaders preferring to take the sea route (in at least one case, a port was constructed explicitly for the purpose of ferrying crusaders). The land route brought with it numerous problems, such as food and supplies for the soldiers and the rest of the camp followers, as well as the potentially sticky situation of marching through foreign, "friendly" territory. In the 1st and 2nd crusades, many if not most of the crusaders seem to have massively underestimated the costs of crusading, and we see plenty of looting of the countryside in order to provide for the soldiers' needs (in fairness, this was due at least in part to markets charging exorbitant prices to the crusaders for food, but nevertheless...). Arrangements were sometimes worked out in advance with local cities and rulers to help ensure safe passage, but even when these agreements were in place events "on the ground" led to raiding, looting, and bloodshed. In the 2nd crusade, the crusaders had such difficulties in Byzantine territory that it seems Louis and Conrad seriously considered attacking Constantinople, though ultimately things were worked out (until 1204, anyway). Once in hostile territory, i.e. Turkish Asia Minor, the crusader armies would have had to rely on foraging for the needs of the army. The situation could often be quite dire, as in the case of the siege of Antioch, where the crusaders were so hard pressed that they began slaughtering their own horses for food (Frankish cavalry was the main military advantage possessed by the crusaders). Foraging parties were also frequently attacked by Turkish/Ayyubid scouts.
For all of these reasons, and more besides, crusade organizers preferred to take the sea route whenever possible. This is not to say that the sea route didn't come with its own host of problems: the upfront costs were much higher and so more centralized leadership and funding was necessary; travel times could vary greatly, and troops didn't always turn up when they were expected; dangerous seas could cause shipwrecks and deplete the manpower of the army; suitable ports were necessary both for departure from Europe and arrival in the East; etc etc. The benefits, however, outweighed these drawbacks, and following the 3rd crusade we don't see any large crusader armies opting for the land route. And, following the fall of Acre in 1291, there would be no European army in the Levant until the invasions of Napoleon in the 19th century.
Hope that this helps, feel free to ask follow-ups or tangential questions!
Sources: God's War by Christopher Tyerman. I can provide more (and more varied) sources if requested, but Tyerman is, in my opinion, the new standard text on the crusades, and contains a wealth of information in often astounding detail.
Follow-up question: How did those armies deal with passing through neutral territory when going to or returning from war?
/u/Porphyrius has given a great answer on travel times, so I won't go into that, but I would like to add some information on supply lines.
The process of planning the march would begin with the leader of the army sending emissaries to the ruler of the area they were seeking to cross, asking not just for permission to cross into the kingdom, but also to hold markets along the way. Peter the Hermit, who lead the People's Crusade, did not cross into Hungary until he had received permission for his followers to be granted trading privileges. And, for much of the journey through Hungary, Peter's army seems to have been mostly peaceful, generally buying their supplies at the required price.
However, Peter could not rely on markets alone. Towns, which acted as a central point for everyone in the area who wanted to sell grain to gather at, were mostly more than a day's march away and, as such, Peter the Hermit had a large baggage train of carts to carry supplies for his followers between each market. He is recorded as having 40 000 men and 2000 carts which, although likely exaggerated, indicates the relative importance of the baggage train. Yet, for all its size, the baggage train likely couldn't have held more than five or six day's supplies for the purported army size.
So, while the markets allowed the crusaders to resupply and acted as central depots from which to draw food, the baggage train enable the army to march through areas between towns which would have had insufficient supplies for a large army.
It was also wise to send word ahead to theoretically sympathetic, non-neutral nations in order to prevent trouble. The trouble at Semlin and Belgrade caused by Peter the Hermit's troops was largely because Byzantine controlled Belgrade refused an advance party a market, probably wary of an army that had not made formal arrangements to pass through in good order. When the sixteen men left behind in Semlin were beaten for an alleged infraction, tensions (and probably a lack of supplies) resulted in the sack of Semlin and, several days later, Belgrade.
Once in Byzantine lands and with Alexios' permission to travel and trade, the army was able to purchase from markets or draw on supplies stockpiled along their route by the Emperor.
Once in non-Christian lands, the armies could forage for their supplies, but this was much less efficient than the markets. Supplies would have to be gathered in from hundreds of sources even in a small geographical area, and the Turks would not only attack foraging parties but might carry off or hide the food. Worse, food could even be damaged or destroyed by the over enthusiasm of the foraging parties. Foraging could, and did, sustain armies, but it was much more uncertain. Edward III's allies, for instance, were forced to return home during his 1339 campaign despite being in rich country on account of having destroyed most of the available food and not having any alternate supply lines. As such, supplies would be stockpiled ahead of the march where possible and could sometimes be purchased from non-Christian sources, or taken as a bribe not to attack a town.
A final note of import is that timing was everything. While Godfrey of Bouillon reached Hungary following Peter the Hermit (and had to negotiate a new set of markets on account of crusader deprivations), he arrived following the harvest, and so there was a surplus for him to purchase. Count Raymond, however, marched during winter and behind the army of Bohemond, making supplies very difficult for him to acquire. The end result was that Raymond experienced constant harassment of his troops as they foraged to survive and, even after receiving letters of safe conduct, his army was still scattered by the Imperial forces, likely because they were still foraging.
Sources