Was it since the birth of Anakin? Or, after Anakin was accepted as a Jedi by the Jedi Council? Or, after some event when Anakin looked special?
Only canonical answers, please. No speculative answers...
“But tell me, Padawan Skywalker, how it feels to have become a member of such a revered group.” “It’s like a dream come true, sir,” Anakin said in genuine sincerity. “A dream come true ... Then you’ve long thought about the Jedi Order and about the Force.” Anakin nodded. “I’ve always wanted to bring justice—” “It’s not for you to decide your destiny, Anakin,” Obi-Wan said. “The Force will guide you.” Palpatine smiled inwardly. Guide you to me, young Skywalker. Dooku had talent, and could be a powerful placeholder. But this seemingly guiless pleasant-faced boy, this Forceful boy, was the one he would take as his appretice, and use to execute the final stage of the Grand Plan. Let Obi-Wan instruct him in the ways of the Force, and let Skywalker grow embittered over the next decade as his mother aged in slavery, the galaxy deteriorated around him, and his fellow Jedi fell to inextricable conflicts. He was too young to be trained in the ways of the Sith, in any case, but he was the perfect age to bond with a father figure who would listen to all his troubles and coax him inexorably over to the dark side.
From Darth Plagueis
That was just after the battle of Naboo. So in fact Sidious chose Skywalker as his heir the first time they met.
Love at first sight. :)
While the other answer is correct, it's Legends canon now. Darth Plagueis is an amazing book and I highly recommend you read it, Legends or not.
As for canon, the only thing I can think about is the end of The Phantom Menace, when Palpatine says to young Anakin:
And you, young Skywalker, we will watch your career with great interest.
Youtube clip with the quote: