Well, the books don't cover Voldie's discovery. But if Dumbledore managed to find out the details years later, then I don't think it would be all that difficult for Tom Riddle to dig up his own history. After all, he did get his father's last name, so it could not have been all that hard to trace.
Mrs. Cole at the orphanage certainly knew that his mother wished him to be named Tom for his father and Marvelo for his grandfather, and she also gave him his father's last name. So finding out about his heritage would have been fairly simple, even if he didn't get the story from Mrs. Cole. He has the name Tom Riddle. It's not that hard to research the last name.
In this link there are over 2,000 with the name of Riddle in the UK. If Voldie was smart (and I think he is) he'd look for those that might share his first name (in case it was a family name) first, so he'd check out anyone with the name Thomas Riddle. And if that person was the right age to have fathered him (dead or alive) he would logically check that out first.
From there, it would just be detective work, talking to people and gathering information. It's left out mainly because it would have been pretty mundane, we would not have learned more about Voldie, and of course, it's from what Dumbledore can gather so it's rather fragmented in bits and pieces.