Это очень сложный и длинный путь, на который может уйти не один год. Начинают с архивов, через которые прослеживается откуда и куда отправлялись люди, но многие архивы были утеряны. Есть специальные организации, которые за плату помогают оптимизировать запросы и ускорить процесс поиска.
Есть определленные сайты архивы
Например вот эти:
http://podvignaroda.ru/?#tab=navPeople_search
Укажите в определенных полях ФИО Вашего деда и год рождение.
Есть специальные сайты про участников ВОВ.Туда можно выложить своего участника,информацию о нём,награды,а можно найти.Так я нашел много информации о своем прадеде