I've been wondering when Dumbledore concluded that Harry was carrying a piece of Voldemort's soul inside him. Did he know immediately, when James and Lily were killed? Or did he have to work it out over the years as he did with the Horcruxes? In Deathly Hallows, Dumbledore tells Snape:
‘Tell [Harry] that on the night Lord Voldemort tried to kill him, when Lily cast her own life between them as a shield, the Killing Curse rebounded upon Lord Voldemort, and a fragment of Voldemort’s soul was blasted apart from the whole, and latched itself on to the only living soul left in that collapsing building. Part of Lord Voldemort lives inside Harry, and it is that which gives him the power of speech with snakes, and a connection with Lord Voldemort’s mind that he has never understood. And while that fragment of soul, unmissed by Voldemort, remains attached to, and protected by Harry, Lord Voldemort cannot die.’
Deathly Hallows - pages 551-552 - Bloomsbury - chapter, The Prince's Tale
When did Dumbledore realize a piece of Voldemort's soul had latched itself onto Harry's soul?
We don't have precise data. There are 3 possibilities:
Definitely, by the time of Christmas of Harry's 5th year (more specifically, the night Arthur was attacked by Nagini and Harry saw it).
As you yourself excellently covered in this answer, Dumbledore performed an experiment that showed that Harry could see through Nagini's eyes because he and Nagini were both containers for Voldemort's soul.
Likely, by the end of Chamber of Secrets:
...Unless I'm much mistaken, he transferred some of his own powers to you the night he gave you that scar. Not something he intended to do, I'm sure...'
'Voldemort put a bit of himself in me?' Harry said, thunderstruck.
'It certainly seems so.'
Now, Harry being 12 years old, he merely expressed himself inarticulately - he meant "put a bit of his abilities in me". But Dumbledore did NOT correct him, instead he confirmed Harry's wording.
Alternately, Dumbledore ALWAYS knew.
There are 2 things indirectly pointing to this conclusion:
In Deathly Hallows, in "Prince's Tale" chapter, we witness Snape and Dumbledore discussing the topic:
... Then Snape said, “I thought…all those years…that we were protecting him for her. For Lily.”
“We have protected him because it has been essential to teach him, to raise him, to let him try his strength,” said Dumbledore, his eyes still tight shut. ...
Dumbledore opened his eyes. Snape looked horrified.
“You have kept him alive so that he can die at the right moment?“
“Don’t be shocked, Severus. How many men and women have you watched die?”
“Lately, only those whom I could not save,” said Snape. He stood up. “You have used me.”
“I have spied for you and lied for you, put myself in mortal danger for you. Everything was supposed to be to keep Lily Potter’s son safe. Now you tell me you have been raising him like a pig for slaughter – “
“But this is touching, Severus,” said Dumbledore seriously. “Have you grown to care for the boy, after all?”
Notice how Snape basically accuses Dumbledore of being an evil cold unfeeling bastard whose only reason for protecting Harry - which Dumbledore had told Snape to do **right after Potters were killed - and Dumpledore doesn't even try to deny it.
Second, Dumbledore was 100% sure from the day Potters were killed that Voldemort would return:
Did I believe that Voldemort was gone for ever? No. I knew not whether it would be ten, twenty or fifty years before he returned, but I was sure he would do so, ... (OotP)
BUT... we know from other discussions that he didn't realize about Horcruxes until he saw the Diary after CoS events.
So, if he wasn't aware of Horcruxes, just how did he know with such certainty that Voldemort would return? Seems like the ONLY possible reason for him would have been to assume that a piece of his soul was "snagged" by Harry.
We know that wasn't an explanation he gave Harry at the end of year 2... but he never was giving people full truth.
Evidence confirming this is his statement in OotP:
I guessed, fifteen years ago," said Dumbledore, "when I saw the
scar upon your forehead, what it might mean. I guessed that it might be the sign of a connection forged between you and Voldemort. . . . it became apparent, shortly after you rejoined the magical world, that I was correct . . . ."
also the dreams that give him flashes of insight into what V is up to throughout book 4. there is a bit where is 'on the floor clutching his scar' or something like that in Trelawney's class isnt there? and then also, in book 2, he saw that harry was a Parselmouth. so you get hints prior to the prophecy reveal in book 5, that they are connected in some weird way.
He probably learnt about who harry was after the chamber of secrets, and was assured of what he was after he realized the weak connection but still a connection between him and the dark lord when harry tells Dumbledore about his dreams in the Goblet of Fire.In the Order of the Phoenix he tells Snape he has to do something or they will be vulnerable, as if he knew what harry was and was scared that Voldemort would learn of this and utilize it to his advantage. I don't know when they realized themselves, but even Ron and Hermione learnt about this special connection, and eventually somewhere in the Order of the Phoenix they realized that he probably was a Horcrux. This is Dumbledore the greatest wizard of his age, he would have probably realized and put the pieces together sooner in the Chamber of Secrets anyways.