Я скажу только про Москву, поскольку не так давно сама вступала в наследство. Вам ответили полнейшую ерунду, когда сказали, что нотариус, якобы, возбуждает розыскное дело (нотариус - не сыщик и не правоохранительные органы). Ничего он не будет "возбуждать", если вы сами к нему не обратитесь (да, и то, он откроет дело о вступлении в наследственное право). Если же вы не обратитесь к нему, то по истечении определённого срока вы это самое право потеряете.
Итак, к какому же нотариусу следует обращаться? Нужно отметить, что сейчас можно обращаться к любому: как к частному, так и к государственному. Кстати говоря, государственных нотариусов не только в Москве, но и во всей стране, осталось по пальцам пересчитать. Да, и расценки на услуги у тех, и других практически одинаковые. Лучше всего выбирать нотариуса по месту прописки умершего, ибо вам придётся собирать большое количество различных бумажек (их список вам предоставит нотариус, который откроет дело о вступлении в наследство), а это лучше делать в том районе/округе, где нотариус работает (рычаги ускорения получения документов ещё никто не отменял, увы:-) В инете можно найти список всех нотариусов по административным округам Москвы (лучше обращаться к тому, рядом с именем которого имеется приписка уполномоченный). После того, как вы обратитесь к нотариусу и он откроет дело в вступлении в наследство, вам ничего другого не останется, как следовать пошаговым инструкциям, которые вы будете от него получать. Если вы всё это будете неукоснительно соблюдать и выполнять, то через 6 (шесть) месяцев (и ни днём раньше) вы вступите в наследство и получите от нотариуса соответствующий документ. Этот же нотариус будет "утрясать" право наследования других претендентов, если таковые имеются. Хороший нотариус всё уладит полюбовно, не доводя дело до суда. Если же споры по урегулированию права наследования имущества умершего разрешить мирным путём не удастся, то придётся обращаться в суд. Но сия процедура уже мне неизвестна, ибо у меня до неё дело не дошло.
И вот тут на БВ я отвечала на похожий вопрос 4 месяца назад - может быть, и это пригодится.