Очень многогранный вопрос. Я могу несколько примеров привести и кое-что из литературы посоветовать.
1. Столиц у государств в нынешнем понимании в Средневековье практически не было, причём в некоторых случаях весьма долго. Германский император Генрих II (конец X - начало XI века) постоянно ездил по германской части империи, несколько раз приезжал в Италию (это за Альпы, между прочим, а потом - обратно), имея обыкновение встречать Рождество в Бамберге. И никого это не удивляло. Существовала система т.н. пфальцев - мест, где император останавливался - со всем кочующим по факту двором. Круги по своей стране император наматывал немалые вплоть до смерти. А один из его предшественников - Оттон II (последняя четверть X века) в некоторый момент по политической ситуации сорвался с места и за пару недель прибыл в Италию, чтобы навести там порядок. Не преуспел, но не в этом вопрос. И в Германии так было ещё очень долго. Карл V - а это уже Раннее Новое время вынужден был ездить по значительно большей территории, потому как без него мало какие места существовали мирно. Масштаб европейской части империи на тот момент даёт представление о временных границах таких путешествий, если учитывать, что ни одна область долго не была без внимания императора.
2. Не хотите брать Германию в пример - возьмём пример Алиеноры Аквитанской (XII век). Эта бабушка (лет ей на тот момент было порядком - около 70, кажется - для того времени очень много) съездила из Англии в Наварру - за невестой Беренгарией для сыночка Ричарда - и повезла сеньориту в Мессину. Обернулась за полгода примерно. Но там никто никуда не спешил. В Наварре время потратилось на переговоры и т.д. Кстати, дорогу невеста перенесла хуже.
3. О том, как ездили в районе 1000 года по Европе, можно найти описания, в основном происходящие из рассказов монахов и дипломатов (хотя не только). Например,
Э. Поньон в "Повседневной жизни Европы в 1000 году" писал(а):
Ришер, монах аббатства Святого Ремигия в Реймсе, был очень увлечён медициной. Он мечтал прочитать "Афоризмы" Гиппократа. <...> к Ришеру приехал посланник от его друга Герибранда, шартрского священника, который приглашал его приехать для ознакомления с этим трудом. В восторге от предложения он решил последовать за этим человеком... и взял с собой слугу из монастыря. Он пишет, что его аббат "дал ему в помощь только одно вьючное животное"; из его последующего описания становится ясно, что у самого Ришера также была лошадь. Итак, трое мужчин отправились в путь верхом. Но Ришер покинул обитель "без денег, без сменной одежды, без каких-либо предметов первой необходимости". <...> верхом при наличии багажа можно было проехать в день 55-60 километров, можно было легко сбиться с пути и некоторые мосты были в ужасающем состоянии. Мы можем также констатировать, что что человек, находящийся в тяжёлом положении, мог провести часть ночи в одиночку с багажом в лесу по соседству с Мо и не быть ограбленным. Наконец мы видим, что монастыри были традиционным местом ночлега для путешествующих, и... что их гостеприимством распространялось не только на путешественников, носивших сутану.
4. А вот о дипломате, на своё несчастье съездившем в Константинополь.
Э. Поньон в "Повседневной жизни Европы в 1000 году" писал(а):
Лиутпранд, епископ Кремоны, отправившийся в 968 году с посольством от императора Оттона Великого в Константинополь, оставил нам живописный рассказ о начале своего возвращения на родину. Василевс и весь византийский двор отнеслись к нему очень плохо. Исполнив свою миссию посла, он затем был вынужден долгое время ожидать разрешения на отъезд и выдачи средств на дорогу. Наконец, 2 октября в сопровождении проводника... он покинул ненавистный ему город Константинополь, "на борту небольшого корабля". Он не сообщает о том, где высадился на сушу, но далее мы читаем, что он ехал "49 дней на спине осла, шёл пешком, скакал верхом на коне, страдая от голода, жажды, задыхаясь, рыдая, стеная", пока не прибыл в Навпактос. Таким образом, он пересёк всю Фракию, Македонию, Фессалию и Этолию, то есть преодолел около 1500 километров, делая переезды приблизительно по 30 километров каждый.
Ну, и много других рассказов есть. Они обычно рассеяны по книгам в микроскопических дозах. Вот можете посмотреть книгу, которую я цитировал (в цитате название и автор). Можно обратиться непосредственно к хроникам - их сейчас можно раздобыть. Только это должны быть хроники не совсем уж старые-престарые, а что-то поближе. Типа Фруассара или Матвея Парижского. Из них даже Дюма подробности для своих книг черпал. Ещё можно почитать о том, как крестоносцы и их последователи добирались в Утремер (например у Т. Эсбриджа в "Крестовых походах").
