Dumbledore suspected that Voldemort was behind the attacks the first time the Chamber was opened, even if he wasn't able to prove anything.
"Only the Transfiguration teacher, Dumbledore, seemed to think that Hagrid was innocent. He persuaded Dippet to keep Hagrid and train him as gamekeeper. Yes, I think Dumbledore might have guessed. Dumbledore never seemed to like me as much as the other teachers did..."
"I bet Dumbledore saw right through you," said Harry, his teeth gritted.
(Chamber of Secrets, Chapter 17, The Heir of Slytherin).
He doesn't need to use Legilimency (and I'm not sure who he'd perform it on, anyway). When the attacks started again Dumbledore knew that Voldemort must have had something to do with it. As soon as he saw the writing on the wall proclaiming the opening of the Chamber he would've known that Voldemort was somehow involved. But he didn't understand how Voldemort could be influencing Hogwarts in his current spirit-like condition. That's why he says the question is not who but how.
He certainly made the link to Voldemort being in the Chamber without Harry telling him.
"What interests me most," said Dumbledore gently, "is how Lord Voldemort managed to enchant Ginny, when my sources tell me he is currently in hiding in the forests of Albania."
(Chamber of Secrets, Chapter 18, Dobby's Reward).
Dumbledore comes out with this unprompted, showing that he knew that Voldemort was involved all along. What he lacked was the knowledge of the diary to understand how Voldemort was able to do it.