For the Democrats, it's State Sen. Creigh Deeds and State Del. Brian Moran. They've basically been running-without-actually-running since the '05 elections were over.
For the Republicans, it's Attorney General Bob McDonnell and Lt. Governor Bill Bolling. There are rumors that Bolling may run in the special election for VA-01; although he doesn't actually live in the district, his old State Senate district lies mostly within the congressional district. There are also the rumors of George Allen making a comeback bid, although I don't know why he would do that -- he'll never be president now, which is the only thing he really seemed to want.
It's interesting to note that, since 1977, Virginians have always elected a Governor from the opposite party of the sitting President. Who knows if there's a correlation there.
New Jersey has done the same since 1989 *I think*. 2009 could break the trend in both states with John Corzine being re-elected in New Jersey and Creigh Deeds winning in Virginia.