While I haven't SEEN the deleted scenes, I get the impression Nero was captured by the klingons after the attack on the Kelvin and his ship escaped.
Nero is imprisoned on Rura Penthe (which explains what he was doing for 20+ years while Kirk and Spock grow up).
His ship eventually returns to spring him, which although not seen(?) is implied when Uhuru says they received a transmission of a Klingon prison planet being destroyed.
It actually ties the movie together better than 'random klingon prison planet has been destoryed'.