Petyr Baelish's claims
You're not wrong in remembering that, Petyr did boast of bedding the Tully girls at court. Both Tyrion and Jaime threw that in face of Catelyn Stark:
In ACOK Jaime said:
Jaime took a swallow, wiped his mouth. “No doubt Ned wished to spare
you. His sweet young bride, if not quite a maiden. Well, you wanted
truth. Ask me. We made a bargain, I can deny you nothing. Ask.”
He also said:
“That name again. I don’t think I’ll f--k you after all, Littlefinger
had you first, didn’t he? I never eat off another man’s trencher.
Besides, you’re not half so lovely as my sister.”
Unlike his brother however, Tyrion believed it to be a lie:
“Why does a bear shit in the woods?” he demanded. “Because it is his
nature. Lying comes as easily as breathing to a man like Littlefinger.
You ought to know that, you of all people.”
She took a step toward him, her face tight. “And what does that mean,
Tyrion cocked his head. “Why, every man at court has heard him tell
how he took your maidenhead, my lady.”
The proof for authenticity and falsehood of his claims
The other answers have successfully established that:
Petyr had indeed slept with Lysa and impregnated her. He however did
not sleep with Catelyn.
One thing that has not been discussed is that Petyr Baelish quite genuinely believes to have bedded both of them. So when he talks about bedding them both, he actually believes it to be true.
Petyr Baelish was brought to Riverrun when Lord Hoster befriended Petyr's father in a military campaign. The Tully girls actually did things in Childhood which lead Petyr on. From AGOT Chapter 71:
How young they all had been-she no older than Sansa, Lysa younger than
Arya, and Petyr younger still, yet eager. The girls had traded him
between them, serious and giggling by turns. It came back to her so
vividly she could almost feel his sweaty fingers on her shoulders and
taste the mint on his breath. There was always mint growing in the
godswood, and Petyr had liked to chew it. He had been such a bold
little boy, always in trouble. “He tried to put his tongue in my
mouth,” Catelyn had confessed to her sister afterward, when they were
alone. “He did with me too,” Lysa had whispered, shy and breathless.
“I liked it.”
Then in ASOS Chapter 45 Catelyn recalls this:
She had played at being Jenny that day, had even wound flowers in her
hair. And Petyr had pretended to be her Prince of Dragonflies. Catelyn
could not have been more than twelve, Petyr just a boy.
Prince of Dragonflies, Duncan "The Small" Targaryen and his lady wife Jenny of Oldstone were Westerosi version of a celebrated couple of lovers like Romeo and Juliet in our world. Sure they were kids back then and Catelyn never meant anything by these gestures but they lead Petyr on a road where he ultimately fell in love with her (At least back then he did).
Then Lysa Tully recalls the Night of Catelyn's betrothal to Brandon Stark in ASOS Chapter 80:
“Be quiet, I haven’t given you leave to speak. You enticed him, just
as your mother did that night in Riverrun, with her smiles and her
dancing. You think I could forget? That was the night I stole up to
his bed to give him comfort. I bled, but it was the sweetest hurt. He
told me he loved me then, but he called me Cat, just before he fell
back to sleep. Even so, I stayed with him until the sky began to
Petyr Baelish was "heartbroken" if we assume he had a heart back then, when Catelyn laughed at him and rejected his attempts to kiss her again. He was drunk when Lysa slipped into his room. They slept together but Petyr believed it was Catelyn who came to him that night, not Lysa1. So that's why Petyr Baelish believes he bedded both the Tully sisters and tells other people about it so confidently that even Tyrion could not be sure who is lying? Petyr or Catelyn?
In the same Chapter Lysa recalls:
Everyone thought it [Petyr's expulsion from Riverrun] was because of
that stupid duel with Brandon Stark, but that wasn’t so. Father said I
ought to thank the gods that so great a lord as Jon Arryn was
willing to take me soiled, but I knew it was only for the swords. I
had to marry Jon, or my father would have turned me out as he did his
brother, but it was Petyr I was meant for. I am telling you all this
so you will understand how much we love each other, how long we have
suffered and dreamed of one another. We made a baby together, a
precious little baby.
Catelyn on the other hands always did her duty as charged by her Lord Father. She had never liked Petyr and she was content with her betrothal to heir to Winterfell, Brandon Stark. Later when Brandon died, She had accepted that she had to marry Eddard Stark instead. And as DariM has already quoted:
And when Brandon was murdered and father told me I must wed his
brother, I did so gladly, though I never saw Ned's face until our
wedding day. I gave my maidenhood to this solemn stranger[Eddard Stark] and sent
him off to his war and his king and the women who bore him his
bastard, because I always did my duty.
1 It is unclear that Lysa ever told Petyr that it was her who came to him that night, not Catelyn. It is also unclear if Petyr ever told Lysa that he believed that it was Catelyn despite uttering her name after having sex. It is possible that Lysa may have told Petyr about that night and since Petyr knew Lysa had to abort the child he left her with, it becomes more plausible that she did. Which would essentially mean that Petyr knew and had been lying deliberately. Nevertheless, since it is my observation, not canon info, I'd dance with what's provided in the canon sources