Чтобы поменять фамилию и получить новый паспорт, в какие гос. учреждения надо обращаться?

Сначала в ЗАГС, потом в Федеральную миграционную службу:

Утверждено
Постановлением Правительства
Российской Федерации
от 8 июля 1997 г. N 828

ПОЛОЖЕНИЕ
О ПАСПОРТЕ ГРАЖДАНИНА РОССИЙСКОЙ ФЕДЕРАЦИИ
10. Выдача и замена паспортов производятся территориальными органами Федеральной миграционной службы по месту жительства, по месту пребывания или по месту обращения граждан в порядке, определяемом Федеральной миграционной службой.
12. Замена паспорта производится при наличии следующих оснований:
изменение гражданином в установленном порядке фамилии, имени, отчества, изменение сведений о дате (число, месяц, год) и / или месте рождения;
13. Для замены паспорта гражданин представляет:
заявление по форме, установленной Федеральной миграционной службой;
паспорт, подлежащий замене;
две личные фотографии размером 35 x 45 мм;
документы, подтверждающие указанные в пункте 12 настоящего Положения основания для замены паспорта.

ФЕДЕРАЛЬНЫЙ ЗАКОН

ОБ АКТАХ ГРАЖДАНСКОГО СОСТОЯНИЯ
Статья 58. Перемена имени

1. Лицо, достигшее возраста четырнадцати лет, вправе переменить свое имя, включающее в себя фамилию, собственно имя и (или) отчество.
2. Перемена имени производится органом записи актов гражданского состояния по месту жительства или по месту государственной регистрации рождения лица, желающего переменить фамилию, собственно имя и (или) отчество.
3. Перемена имени лицом, не достигшим совершеннолетия, производится при наличии согласия обоих родителей, усыновителей или попечителя, а при отсутствии такого согласия на основании решения суда, за исключением случаев приобретения лицом полной дееспособности до достижения им совершеннолетия в порядке, предусмотренном законом.
4. Перемена имени лицу, не достигшему возраста четырнадцати лет, а также изменение присвоенной ему фамилии на фамилию другого родителя производится на основании решения органа опеки и попечительства в порядке, установленном статьей 59 Семейного кодекса Российской Федерации.
5. Перемена имени подлежит государственной регистрации в органах записи актов гражданского состояния.

вы не поверите: в ЗАГС.. .
хоть на фамилию Путина...

Сначала нужно придумать повод для смены фамилии.
Это может быть брак - тогда в ЗАГС.
Или писать заявление в паспортный стол о том что вы считаете свою фамилию
неблагозвучной или непристойной.

Паспортный стол

в паспортный стол

нельзя поинтересоваться фамилией?)))

если сама меняеш фамилию - тоесть не выходя замуж а просто твоя не нравится, то в закс где тебе свидетельство о рождении выдавали, а потом в паспартный стол!