Для начала поиска необходимо максимально собрать имеющуюся дома информацию о погибшем/пропавшем без вести: имя, фамилия, отчество, дата и место рождения. Если сохранились фотографии, письма с фронта, их нужно изучить на наличие сведений о месте службы, звании и роде войск. Важно определить в войсках каких Народных Комиссариатов служил человек: Народный Комиссариат Обороны (сухопутные войска и авиация), Военно-Морской Флот (в том числе береговые части и авиация ВМФ), Народный Комиссариат Внутренних Дел (войска НКВД, пограничные части). От этого будет зависеть, в какой архив вы будете в дальнейшем обращаться.

Если сохранились письма с фронта, на них обычно указывался номер полевой почты. По этому номеру ППС иногда можно определить название воинской части.
Справочник полевых почтовых станций РККА в 1941-1945 гг.

Если сохранились награды, по их номерам также можно определить номер воинской части и даже узнать описание подвига или боевых заслуг награждённого.

Министерство Обороны РФ продолжает рассекречивать большой массив документов, касающихся периода Великой Отечественной войны. ЦАМО (Центральный архив Министерства Обороны) их оцифровывает и пополняет электронные базы данных. Проверяйте наличие сведений на своего родственника по этим базам:
ОБД "Мемориал" (инструкция, как искать на сайте здесь)
Память народа
Подвиг народа - сайт, где можно проверить наличие наград

Внимательно проверяйте все базы. Не спешите. В военных документах часто встречается много ошибок. У вас даже могут появится не просто однофамильцы, но и полные тезки разыскиваемого родственника, у которых какие-то факты биографии совпадают с нужными Вам. Все собирайте в одном месте и обязательно для каждого факта указывайте источник, из которого Вы его получили. Спустя какое-то время у вас могут появиться новые сведения, которые заставят вас пересмотреть все уже известное ранее.

По разным данным в немецком плену побывало около 5 млн советских граждан и военнослужащих. Около 3 млн человек погибли. Освобожденные военнослужащие направлялись в проверочно-фильтрационные лагеря (ПФЛ) НКВД, где следователи отдела контрразведки "Смерш" выясняли обстоятельства пленения и условия содержания в концлагере.

То, что все военнослужащие, освобождённые из немецкого плена, осуждались в СССР на 10-25 лет и направлялись в советские концентрационные лагеря я является ложью. В тех случаях, когда детальная проверка не требовалась, человек не сотрудничал с лагерной администрацией, не доносил и никак себя не запятнал, фильтрационное дело не заводилось, составлялась только карточка, а военнослужащего направляли в запасной стрелковый полк. В других случаях бывшие военнопленные могли быть направлены в штрафные роты (офицеры при этом обычно лишались званий). Срок пребывания бывших военнопленных в ПФЛ обычно не превышал одного-двух месяцев.

Фильтрационное дело следует искать в областных и республиканских архивах ФСБ в регионе места жительства или рождения военнослужащего.
Поиск интернированных граждан, узников концлагерей и военнопленных
Список советских военнослужащих, погибших в финском плену в 1941-1944 гг.
Советские военнопленные

Картотека погибших и пропавших без вести военнослужащих НКО за годы Великой Отечественной войны хранится в Центральном архиве Министерства Обороны (ЦАМО). Такие же картотеки имеются и в других архивах:
а) Центральный Военно-морской архив в г. Гатчина - по личному составу флота, береговой службы и авиации ВМФ,
б) Российский государственный военный архив (РГВА) в г. Москва - по сотрудникам органов, соединений и частей НКВД,
в) архив Федеральной пограничной службы ФСБ РФ в г. Пушкино Московской области - по пограничникам,
г) Военно-медицинский архив в Санкт-Петербурге - по военным медикам и по ранениям всех остальных.

Если ваш родственник был офицером, весьма вероятно, что в архиве могло сохраниться его личное офицерское дело. Чтобы сделать запрос на его получение, необходимо к запросу приложить пакет из копий документов, подтверждающих ваше родство с тем человеком. К сожалению, на рядовой и сержантский состав личные дела не заводились, поэтому количество документов, которые можно пытаться найти, значительно меньше.

Если известно место призыва, есть смысл попробовать сделать запрос в военкомат того населенного пункта, откуда человек был призван. В военкомате могут храниться как списки мобилизованных / добровольцев, так и документы об их гибели или пропаже без вести, ранениях, награждениях, демобилизации, а также иногда могут быть и вторые экземпляры личных офицерских дел.

Будьте готовы к любому исходу поисковой работы: вы можете как найти довольно большой объем сведений о своем родственнике, так и почти ничего не найти. Ищите помощь на профильных форумах, находите поисковиков, общайтесь с ними, проверяйте их базы данных поднятых солдат и установленные имена во время вахт, если известен регион гибели. Эти данные ежегодно пополняются. Вдруг вам повезет и вы найдете своего бойца.

Первый и единственный учебник по военному поиску, адресован широкому кругу читателей, интересующихся судьбами участников Великой Отечественной войны,
также – историкам, генеалогам, краеведам, журналистам и писателям.
Альманах "Генэкспо" - 2. Все грани памяти
Рабочая тетрадь по военному поиску