можно спросить в справочной на вокзале, можно и просто пройтись вдоль по улице. естественно, что забронировать номер будет надежнее чем искать отель по приезду, да и дешевле зачастую. например, в Штутгарте можно за 24 евро с человека за ночь поселиться в **** отеле , а можно и за 55 в **. отели можно присмотреть на
http://www.hrs.com ,
http://www.hotelreservierung.de хотя там конечно же не все отели. самые дешевые варианты ищутся по ключевым словам Jugendheim/Jugendherberge/Herberge/Ferienwohnung/Pension
http://www.unterkunft.de ,
http://www.FeWo-direkt.deесли я правильно понял, у Вас получается на каждый город по одному дню и еще один остается "про запас". очень рекомендую посетить на пути из Мюнхена во Франкфурт Нюрнберг или Вюрцбург. В Нюрнберге можно просто походить по центру, посетить дом-музей Альбрехта Дюрера
http://de.wikipedia.org/w/index.php?title=Datei:Nuremberg_Duererhaus_f_n.jpg&filetimestamp=20041114112321, осмотреть крепость. В Вюрцбурге
http://de.wikipedia.org/wiki/W%C3%BCrzburg шикарную "Зимнюю резиденцию"
http://de.wikipedia.org/wiki/Residenz_W%C3%BCrzburg Residenz [рЕзиденц] (именно с ударением на первом!! слоге, а то могут и не понять с замечательным парковым комплексом. еще там чудный цетр с церквями, соборами, фонтанами и пр. старинный мост через Майн
http://de.wikipedia.org/wiki/Alte_Mainbr%C3%BCcke и сказочный вид с него на замок-крепость на горе (там несколько музеев внутри и вид с высоты птичьего полета на город и реку).
честно говоря, я бы Франкфурт вообще пропустил. город как город. ну пара небоскребов в центре. особого впечатления на меня он не произвел.
а насчет проезда, конечно, автостопом - это самый дешевый вариант, но и самый "стремный", по ж/д ехать гораздо проще и удобнее (к примеру, можно на любой станции сойти, погулять и поехать следующим поездом через часик-два-три...), но для этого нужны довольно таки приличные деньги. так, например, билеты на троих от Страсбурга до Штутгарта стоят от 80 с хвостиком евро. это если покупать билет от А до Б , но есть вариант значительно дешевле: от Страсбурга до станции Kehl [Кель] это 3,60 с носа и 10 минут езды и вот вы уже из Франции попали в Германию, а тут уже можно купить Baden-Württemberg-Ticket [Баден-Вюртемберг-тикет] всего за 28 евро. по нем можно всем троим во всему Баден-Вюртембергу (в том числе и по Штутгарту) целый день ездить, правда кроме поездов типа ICE и только вторым классом. в каждой земле в Германии есть свой Ticket, в Баварии - это байернтикет, в Эссене (Hessen - Frankfurt) - хессентикет ну и т.д. в принципе, можно купить билет байернтикет и хессентикет и на них доехать от Мюнхена до Франкфурта и это будет стоить 2х28 = 56 евро на троих. ну и т.д.
я так понял по вопросам про жилье, что Ваш бюджет сильно ограничен или вы просто любите путешествовать автостопом?
лично я предпочел бы поездку на поезде и отель не ниже **** (вариант подешевле) но тут уж решать, конечно, Вам.