At the most basic level we could simply presume that Ollivander was part of the minority who was familiar with the progression of Tom Riddle to Voldemort. The reason why most people wouldn't have known that Voldemort was Tom Riddle is that when Voldemort became famous (or infamous) he already went by the name Voldemort so anyone who didn't already know him would have no reason to connect him to Tom Riddle. But for those who did know him beforehand – and Ollivander was one such person – it wouldn't actually have been that hard to make the connection. Already at school Riddle had a gang of followers; when he became Voldemort he had many of the same followers, which would point to his identity as Tom Riddle. His physical transformations happened over a period of time, so someone paying attention could have noticed the progression from Riddle to Voldemort. Indeed, the description of Voldemort at a time when he already went by that name, seems to indicate that he hadn't completely lost the look of Tom Riddle:
Harry let out a hastily stifled gasp. Voldemort had entered the room. His features were not those Harry had seen emerge from the great stone cauldron almost two years ago: They were not as snakelike, the eyes were not yet scarlet, the face not yet masklike, and yet he was no longer handsome Tom Riddle. It was as though his features had been burned and blurred; they were waxy and oddly distorted, and the whites of the eyes now had a permanently bloody look, though the pupils were not yet the slits that Harry knew they would become. He was wearing a long black cloak, and his face was as pale as the snow glistening on his shoulders.
Additionally, it seems that this wasn't just any case of Ollivander just coincidentally remembering facts about wands. In Chapter Thirty-Six of Goblet of Fire we find the following:
"Yes, said Dumbledore. "Mr. Ollivander wrote to tell me you had bought the second wand, the moment you left his shop four years ago."
Writing to Dumbledore the moment Harry left the shop seems like overkill for something that was merely (as described by Ollivander) "curious". This passage almost makes it seem like Dumbledore had previously arranged with Ollivander to let him know as soon as that wand was purchased. Indeed, in the same chapter Dumbledore says that the feathers for the wand cores came from his own phoenix; coupled with Ollivander's statement back in Philosopher's Stone that these were the only two wands made from that phoenix, it would certainly not be a stretch to think that Dumbledore had given Ollivander the feathers and specifically asked him to keep track of those wands. If that is the case, then Ollivander could have found out that Voldemort was Riddle in a very straightforward way – Dumbledore might have told him within the very context of a discussion of the twin wands.
With a bit of speculation we can perhaps go even further. Ollivander makes a statement about Voldemort's wand that seems to be interestedly worded. In Chapter Twenty-Four of Deathly Hallows we find:
"The Dark Lord," said Ollivander in hushed and frightened tones, "had always been happy with the wand I made him — yew and phoenix feather, thirteen-and-a-half inches — until he discovered the connection of the twin cores. Now he seeks another, more powerful wand, as the only way to conquer yours."
Notice the words "the wand I made him". Ollivander doesn't generally make specific wands for specific people. When children come to buy their wands they try out already made wands until they find one that "chooses" them. If young Tom Riddle had bought the phoenix wand in the regular fashion, it would seem a bit odd to describe it as a wand made for him when in fact it was just a generic wand that ended up choosing him.
This can perhaps be an indication that the phoenix wand was not the original wand that Tom Riddle bought. Instead it may have been a wand that Ollivander specifically made for him after he was already Voldemort. In that case Ollivander wouldn't have to know that Riddle and Voldemort were the same person; he would simply know that the wand belonged to Voldemort.
As for why Ollivander would have made Voldemort a new wand, there can be any number of explanations. Perhaps his first wand broke, perhaps his first wand wasn't well suited to the boundary-pushing-magic that Voldemort wanted to perform. Voldemort might even have forced him to make a new one. Indeed, another particularly-worded passage might possibly support this:
"No," said Voldemort. "I have performed my usual magic. I am extraordinary, but this wand ... no. It has not revealed the wonders it has promised. I feel no difference between this wand and the one I procured from Ollivander all those years ago."
The word "procure" is not one that is all that common in everyday conversation. People don't usually use it to refer to something that they just happened to come into possession of. Indeed, the first definition in Merriam-Webster is:
to get possession of (something) : to obtain (something) by particular care and effort
The use of this word would make perfect sense if Voldemort had gone out of his way to get this particular wand, e.g. by having it custom-made by Ollivander. In fact, I think every other usage of this word in the series is in reference to something that was specifically gotten, hard to get, or obtained by force.
Remember also that Ollivander glorifies Voldemort's achievements with the phoenix wand ("great but terrible"). Even though Ollivander didn't necessarily support Voldemort, it might be well within character for him to specifically make Voldemort a special wand to help him achieve "greatness".
Alternatively, this could have been one of Dumbledore's schemes. For all we know he may have deliberately caused Voldemort to get the phoenix wand so that he could then ensure that someone else could have a twin wand which might be able to be used against Voldemort. While this seems improbable at first glance, it doesn't seem so crazy for Dumbledore – when he noticed the path Voldemort was taking – to come up with every possible means of stopping him. If it meant tricking Voldemort into taking one of a pair of wands so that someone else could later use the twin cores advantageously, that might be something Dumbledore would try. In any such scenario it would certainly make sense that Ollivander – as the wandmaker – would be in on the plan, and therefore know that Tom Riddle and Voldemort were the same person.
In short, while we can't say for certain how Ollivander made the connection between Tom Riddle and Voldemort, it doesn't seem at all unreasonable that he was able to do so.