We know that Dumbledore knew about Horcruxes at least as early as Harry's parents' deaths (he stated to Snape that Voldemort would be back).
And in Harry's 6th year, he knew that there were 7 for sure, from real Slughorn memory.
At which point did he find out or at least have a good guess that there were >1?
Dumbledore had a good guess during Harry's second year, and confirmation, apparently, during Harry's fifth year that he was on the right track:
Rosi: What does ‘in essence divided' mean?
J.K. Rowling: Dumbledore suspected that the snake’s essence was divided – that it contained part of Voldemort’s soul, and that was why it was so very adept at doing his bidding.
J.K. Rowling: This also explained why Harry, the last and unintended Horcrux, could see so clearly through the snake’s eyes, just as he regularly sees through Voldemort’s.
J.K. Rowling: Dumbledore is thinking aloud here, edging towards the truth with the help of the Pensieve.
LEAKY CAULDRON - 7.20.07 - WEB CHAT TRANSCRIPT
JKR's quotes refer to this passage from Order of the Phoenix:
‘Naturally, naturally,’ murmured Dumbledore apparently to himself, still observing the stream of smoke without the slightest sign of surprise. ‘But in essence divided?’
Harry could make neither head nor tail of this question. The smoke serpent, however, split itself instantly into two snakes, both coiling and undulating in the dark air. With a look of grim satisfaction¹, Dumbledore gave the instrument another gentle tap with his wand: the clinking noise slowed and died and the smoke serpents grew faint, became a formless haze and vanished.
OOTP - page 416 - UK - chapter 22, St. Mungo's Hospital for Magical Maladies and Injuries
I have a different take on when Dumbledore knew about Horcruxes being involved, which JKR addresses above with her ‘he was edging towards the truth' comment. I do not believe Dumbledore knew at the time of James and Lily's death that Horcruxes were involved. It wasn't until Chamber of Secrets that he becomes aware that the diary had contained very rare, very dark magic.
ETA: I need to self-correct here. Dumbledore suspected more than one Horcrux during Harry's second year, after Voldemort treated the diary Horcrux so casually. Dumbledore figured he must have, or have been planning to make more than one:
‘The careless way in which Voldemort regarded this Horcrux seemed most ominous to me. It suggested that he must have made – or been planning to make – more Horcruxes, so that the loss of his first would not be so detrimental. I did not wish to believe it, but nothing else seemed to make sense.
Half-Blood Prince - page 469 - UK - chapter 23, Horcruxes
and then during Harry's fourth year, after Voldemort regained his body:
‘Then you told me, two years later, that on the night that Voldemort returned to his body, he made a most illuminating and alarming statement to his Death Eaters. “I, who have gone further than anybody along the path that leads to immortality.” That was what you told me he said. “Further than anybody.” And I thought I knew what that meant, though the Death Eaters did not. He was referring to his Horcruxes, Horcruxes in the plural, Harry, which I do not believe any other wizard has ever had.
Half-Blood Prince - page 470 - UK - chapter 23, Horcruxes
¹JKR's quote suggests that Dumbledore smiled in grim satisfaction because it was confirmed he was on the right track, but that it was a terrible path to navigate. When he saw the two snakes, it was the first confirmation he had of Voldemort splitting his essence, his soul, thus that the possibility of Horcruxes was high.
