какой "штамп с новой фамилией"? с новой фамилией может быть только ее новый паспорт. правильно я поняла, она хочет поменять свою фамилию на вашу (уже поменяла) и хочет, чтобы это было зафиксированно в ее паспортах?

если у нее российское гражданство и российская прописка - ехать ей в Россию в ее ЗАГС и писать заявление о смене фамилии на основании замужества. т.е. такая стандартная процедура, как при обычном браке.
везете для нашего ЗАГСА св-во о браке, переведенное на русский, заверенное и обязательно апостилированное. общегражданский российский паспорт у нее заберут и скажут, через сколько месяцев (1,2,3???) она может опять приехать и забрать новый паспорт с новой немецкой фамилией. т.е., как видите, ехать придется дважды. по-моему, документы они за границу не высылают. а было бы неплохо...
с новым российским паспортом она возвращается обратно в Германию и в консульстве подает заявление об обмене своего загран.паспорта на новый в связи с изменением фамилии. наше консульство в Германии ничего не будет менять, пока вы не поменяете российский паспорт и не привезете им...
в ЗАГС надо обязательно звонить и все выяснять заранее, кому какие документы нести. может, им сейчас что-то, кроме св-ва о браке, понадобится. и потом - я все на лучшее надеюсь - может, по почте заверенные и апостилированные копии докумемтов им можно отпрвлять. а форму заявления скачать, распечатаь, заполнить и - туда же...
у меня схожая ситуация. сижу и думаю: нужен мне этот "головняк" с обменом паспортов и фамилий или так поживу?