Would the Ministry have been alerted to a young child with magical potential and then told Dumbledore?
How did Dumbledore first find out about the existence of young Tom Riddle?
The Headmaster of Hogwarts would be privy to the information about Tom Riddle's birth. All children with magical abilities (either upon birth or when they first display magical talent) have their name and birthdate are magically inscribed by the Quill of Acceptance into the Book of Admittance. From Pottermore:
At the precise moment that a child first exhibits signs of magic, the Quill, which is believed to have been taken from an Augurey, floats up out of its inkpot and attempts to inscribe the name of that child upon the pages of the Book (Augurey feathers are known to repel ink and the inkpot is empty; nobody has ever managed to analyse precisely what the silvery fluid flowing from the enchanted Quill is).
The Headmaster or Headmistress has access to the tower where the Book and Quill reside. At the time Harry Potter attends Hogwarts, so does McGonagall (presumably because she's Deputy Headmistress), who has the task of checking the book every year and invite the admitted children. From a webchat with JKR:
How can two Muggles have a kid with magical powers? Also how does the Ministry of Magic find out these kids have powers?
A. It's the same as two black-haired people producing a redheaded child. Sometimes these things just happen, and no one really knows why! The Ministry of Magic doesn't find out which children are magic. In Hogwarts there's a magical quill which detects the birth of a magical child, and writes his or her name down in a large parchment book. Every year Professor McGonagall checks the book, and sends owls to the people who are turning 11.
As this answer also explains, the Ministry is not alerted of young children with magic potential, Hogwarts is alerted directly.
Of course, at the time Tom Riddle's name was inscribed in the book (either upon his birth to a pureblood witch or when he first displayed signs of magic in the orphanage where he grew up), Dumbledore was not Headmaster of Hogwarts; that was Armando Dippet.
The Harry Potter wikia says that Dumbledore served as Deputy Headmaster under Dippet, but does not provide a source:
Professor Dippet's term as headmaster ended between March 1965 and March 1971. His immediate successor in the post was Professor Albus Dumbledore, who had been Dippet's Deputy Headmaster and Transfiguration teacher.
At any rate, it seems as though he did carry out the same office as McGonagall later would do when it came to informing parents and children of Hogwarts admittance. He learned of Riddle's existence at some point between his first signs of magic and when he was eleven years old (either from Dippet or directly from the Book as part of these duties). At that point he only knew his name and birthdate, however.
When Riddle was eleven years old he was visited by Dumbledore at the orphanage and informed of his status as a wizard and of the school's existence. We see this scene as a Pensieve flashback in Harry Potter and the Half-Blood Prince. Dumbledore then properly learned of Riddle's existence, but not the extent of his dark nature (although he always kept the knowledge of Riddle's magical misdeeds at the orphanage at the back of his mind).
Harry Potter: "Did you know, sir? Then?..."
Albus Dumbledore: "Did I know that I had just met the most dangerous Dark wizard of all-time? No."