To summarize, they were captured by Klingons shortly after the battle with the Kelvin. Then during his time on a Klingon prison planet, which was planned to be Rura Penthe (the same planet Kirk and McKoy were imprisoned on in The Undiscovered Country), they determined when Spock would arrive. They escaped in time to show up when Spock arrived, and they promptly captured him.
It's unclear where the Klingons kept the Narada, which would have been a pretty big boon to their engineers. (There are Klingon engineers, right?)
From Memory Alpha:
Nero spent the next twenty-five years awaiting the arrival of Ambassador Spock, plotting his vengeance against him and the Federation. Near the end of those twenty-five years, Nero was involved in an attack on a Klingon prison planet and, using the Narada, destroyed 47 Warbirds. During his time on the prison planet, Nero sustained an injury to his right ear.
This was covered in a deleted scene:
A deleted scene from the film shows Klingons surrounded the Narada following George Kirk's attack, and Nero and his crew gave themselves up to be imprisoned on Rura Penthe. During his time on the planet, Nero kept quiet about his origins, and lost part of his ear, escaping with his crew after the Klingons discovered his calculations regarding Spock's arrival and threatened to interrogate him with a centaurian slug. It was his escape from Rura Penthe that Uhura heard about in the transmission she received regarding an attack on a Klingon prison planet.