I think you need two 6 pin PCI express power connectors. I also agree the 850W might be a good choice, power supplies operate at their best efficiency around 50% load. Plus its nice to have a PSU that will grow with you.
I'd say look for a 5 year warranty. Its up to you if you want a certification. I have a NZXT Hale 90 Gold which I paid about $140 for that I am very happy with, its a Super flower and a top rated model. It is almost completely modular, with only the 24 pin and 12V ATX 4/8 pin being hardwired. As a modder, I prefer modular supplies. If you can get a gold rating and modular for around $150, that will be a great power supply.
I like Enermax, Antec, Corsair, some Kingwin models, and XFX is coming out with some nice ones. And Seasonic who is actually the OEM some of the better PSUs out there, including corsair and Antec.
Check Jonnyguru for reviews. There are some real gems out there that may not be the most popualr model, its the components that really matter. I think the high current gamer series from Antec is nice.