Pagans who were wicked by pagan standards are punished in the circle of Hell appropriate to their particular crimes. For example, Paris is punished in the second circle for crimes of lust, while Brutus is consigned to the jaws of Satan himself for treachery against his lord and benefactor. Pagans guilty of such sins as suicide and sodomy — sinful by Christian standards but not necessarily by pagan ones — are not specifically punished for them.
Pagans who lived lives of virtue (reckoning, again, by their own pagan standards), but who never had the opportunity to receive Christianity and baptism, are consigned to Limbo — which, though it is technically the first circle of Hell, is not a place of punishment. In fact, it seems to be pretty much what virtuous pagans expected after death. Their only punishment is that they now know that there is something higher — the true Paradise — but have no hope of ever attaining it.
Virtuous Hebrews who lived before Christ could be considered Christians avant la lettre (because they worshiped Jehovah, who is Christ), but they lacked explicitly Christian faith, hope, and baptism. They were consigned to Limbo with the pagans until after the Crucifixion, when Christ came to hell and liberated them. They are now in Paradise.
Note, then, that prior to the Crucifixion everyone (barring perhaps a few exceptions like Enoch and Elijah) went to Hell — either to Hades (Limbo) or Tartarus (the lower circles). This is consistent with most pre-Christian beliefs about the afterlife; certainly no Greek expected to ascend to Olympus after death.
Muslims are considered Christian heretics (a view which is not historically unreasonable), and Muhammad himself is punished as such in the sixth circle of Hell. Other Muslims, though, seem more often to be judged as if they were pagans. Averroes, Avicenna, and Saladin are found in Limbo with the pagan worthies. This despite the fact that, like all Muslims, they lived during the Christian era and could in theory have become Christians had they wished. (Saladin, in particular, had certainly been exposed to Christianity and rejected it; he spent his career fighting against the Crusaders.) I am not aware of any post-biblical Jews who appear in the Comedy, but Dante would perhaps have treated them similarly.
Virgil’s permanent home is in Limbo with the other virtuous pagans, but he is allowed to visit Purgatory in his capacity as Dante’s guide. Paradise, however, is closed to him.
Cato the Younger works as the gatekeeper and guardian of Purgatory. It is not evident what his ultimate fate will be, but it seems reasonable to assume that his situation is similar to that of Virgil: He is visiting Purgatory “on business,” as it were, but in the end — when Purgatory is done away with — will have to return to Limbo. (Note that he is not condemned for his famous suicide — a sin normally punished in the seventh circle of Hell — because it was not forbidden by the Stoic morality under which he lived.)
Trajan, the Roman emperor, is in Paradise, though originally he had been consigned to Limbo like any other righteous pagan. Legend has it that Pope Gregory the Great, saddened at the damnation of so great a man, prayed for his soul and was granted this miracle: Trajan, after all those centuries, was raised from the dead. Back in his body, he was once again free to choose Christianity and baptism, and he did so. When he died for the second time, he went to Paradise as a Christian.
Ripheus is hardly a household name, but he makes a brief (two-line) appearance in the Aeneid, where he is described as “first among the Teucrians for justice and observing right.” Virgil, ever the pessimist, dryly adds that “the gods thought otherwise” — apparently unimpressed by his outstanding virtue, they allow him to be cut down like any common soldier in the sack of Troy. But according to Dante (who apparently invented the story himself), one particular God was impressed with Ripheus’s virtue and chose to reward it by granting him, centuries before the birth of Christ, a private revelation of the Christian gospel. Thus, unknown to his contemporaries, Ripheus died in the true Faith. He lived before baptism was available, but faith, hope, and charity took the place of that sacrament for him. In this he is similar to the pre-Christian Hebrews, who are also saved without baptism — and we may presume that, like them, he went first to Limbo and only later, after Christ’s harrowing of Hell, to Purgatory and Paradise.