Скорее всего, Дамблдор узнал на втором курсе обучения, когда Гарри проявил способности к парселтангу (змеиный язык), так как этот язык перешел к Гарри непосредственно от Вольдеморта.
Судя по всему, окончательно — в пятом томе, когда Гарри увидел глазами Нагайны нападение на Артура Уизли. Но подозрения у Дамблдора были и раньше: уже сразу после первого падения Вольдеморта он обращал внимание на шрам Гарри Поттера.
Серьезные подозрения точно были еще с тех пор, когда Дамблдор узнал, что Гарри змееуст. Он еще тогда сказал, что "Волдеморт что-то передал тебе от себя, когда оставил тебе этот шрам".
На 5 курсе эти подозрения на 100% подтвердились.
Спасибо за ссылки. Совсем по другому взглянула на труды Дж. Роулинг.
Вероятно, он догадался во второй части, когда Гарри контактировал с Томом Редлом и говорил на парселтанге, но скорее всего в шестой, когда Дамблдор подослал его к профессору Слизнорту, иначе это не имеет смысла.