Since my access to the forum crashed late last night (did others experience it as well?) I hacen't replied yet, but now I've been beaten to the point by Berengar. I fully concur with him but can't help to elaborate...
Pregrinato
In the middle ages pilgremage was much more than "just" the travel to shrines and holy sites. It was a concept encompasing all of your life - an allegory of entire life being a journey from birth to death, encountering many hardships yet still trying to ensure that on your deathbed you would reach your final destination - heaven. Some medieval writters were confouned at what the exact point of this pilgrimage was: to try to make a better earthly Utopia before passing to the post mortem Utopia, or was it just to pass throu the ritual test to be granted access to heaven? The concept of all life as a pilgrimage and the veneration of saints were factors in the "travelling" pilgrimages.
Most pilgrimages were local to shrines of important saints or places with a history of miracles. Major sites in Europe was not only Rome but also especially Compostella in Spain (where to this day many still walk the amazing pilgrim route from France and across the Pyreenes on foot). The pilgrimages were an important factor in economy, local benificiaries gaining huge revenues from the pilgrims (which might have promted the extensive importance for church/secular leaders interest in securing relics from saints to local cathedrals and churces).
Today, the pilgrimages to the Holy Land are perhaps the most know, not least because of the crusades (that among many other things were percieved as armed pilgrimages). But many christians had travelled there throughout the centuries prior to the crusades and mostly without incident or hindrance from the local muslim lords and population.
The pilgrimages are well documented - many texts remain written by pilgrims enroute and there are even examples of letters being adressed to pilgrims thus being constantly redirected. Some even did pilgrimages by proxy! Either paying trusted vassals or a hermit, in life or as a part of their testament. Some had even had wax effigies made to go on such journies. Pilgrimage wasn't only a willing effort - for what ever reason - but in some instances it was actually a commonly used punishment or sanction. If you wonder why, remember that one seldomly sentenced transgressors to incarceration (as today - rather using other more physical punishments...), but sending someone on pilgrimage didn't just work to prove their penance but also as a vent for sentiments to cool if local local relationships were becoming too tense. Even lords took to pilgrimages, sometimes in the shape of crusades, to avoid other more unwanted sanctions for whatever transgressions they might have committed...
The road to the destination varied a lot, as earlier stated by my sodales, but I think Brindisi was especially popular partly because of the good roads down the Italian peninsular, the opportunity to pass Rome and finally because there was good traveling opportunities from Brindisi - either by ship directly to the Levant or just shipping across the Adriatic to Dyrrachium, where one could take the land route across Greece and Anatolia.
Kingdom of Heaven gets some things right and other horrible wrong, but that's Hollywood for you! I enjoyed it, I'll readily admit. And the soundtrack has become a staple in my repetoire for our sessions. Messina might have been a "gateway to tje Holy Land" but so might many other towns. Actually the third crusade (1190-91 as a reaction to some of the events in Kingdom of Heaven) passed through Messina, but it really originated or set sails from the ports of Genoa and Marseille. Especially Marseille had the major advantage for Northern/Western Europeans that it enabled them to avoid the strenous passing of the Alps. By the way these two towns also saw the disastrous 1212 Children's Crusade - thousand of children, and others, headed for the Holy Land gaining passage on ships from Marsaille and Genoa - many ships whrecked at sea but more distressing, the children that survived where simply sold as slaves.....
If your group sets out within the empire than maybe it would make most sense to have them continue their travelling within the empire and then passing the Papal State and Rome and onward through the Kingdom of Sicily/Naples - the last one was actually at the time, depending on your saga's timeframe, held by the emperor, as king, which entail some larger security for people of his own realm, even though the two were seperate entities. Then onward it would depend on whether you prefer an exiting journey at sea or across land passing Constantinople and Anatolia. Then there's the other option of setting out from Venice, a city of many sights and with a crucial role in the Roman Tribunal (according to the only sourcebook published, all the local covenants having a house here and plenty of hermetic intrigue).
See - now I've lost myself once more.... long posts.... must stop...
Here are some links that might be useful:
General info and some nice pictures:
http://www.mainlesson.com/display.php?author=tappan&book=bold&story=crusades
http://194.3.120.243/humanities//vs/pilgrims/journey.htm
Some witness accounts from pilgrims:
http://www.newadvent.org/cathen/08254a.htm
Books for further inspiration:
http://www.wsu.edu:8080/~hanly/chaucer/coursematerials/interactive/5062.543.html
Nice site on Kingdom of Heaven (couldn't url it...so copy it manually into your browser - and remember to add the "(film)"):
en.wikipedia.org/wiki/Kingdom_of_Heaven_(film