They left when Robb married Talisa. However in the book this was another girl, Jeyne Westerling. From A Storm of Swords:
“Your wife is lovely,” Catelyn said when they were out of earshot,
“and the Westerlings seem worthy... though Lord Gawen is Tywin
Lannister’s sworn man, is he not?”
“Yes. Jason Mallister captured him in the Whispering Wood and has been
holding him at Seagard for ransom. Of course I’ll free him now, though
he may not wish to join me. We wed without his consent, I fear, and
this marriage puts him in dire peril. The Crag is not strong. For love
of me, Jeyne may lose all.”
“And you,” she said softly, “have lost the Freys.”
His wince told all. She understood the angry voices now, why Perwyn
Frey and Martyn Rivers had left in such haste, trampling Robb’s banner
into the ground as they went.
“Dare I ask how many swords come with your bride, Robb?”
“Fifty. A dozen knights.” His voice was glum, as well it might be.
When the marriage contract had been made at the Twins, old Lord Walder
Frey had sent Robb off with a thousand mounted knights and near three
thousand foot. “Jeyne is bright as well as beautiful. And kind as
well. She has a gentle heart.”
It is swords you need, not gentle hearts. How could you do this, Robb?
How could you be so heedless, so stupid? How could you be so... so
(Bolded the important parts of the quote.)