Sachverhalt: A. Am 29. Mai 2006 schlossen die Y._ AG (Verkäuferin) und A. und B. X._ (Käufer) einen als "Kaufvertrag" bezeichneten Vertrag ab. Darin verpflichtete sich die Verkäuferin, eine 4,5 Zimmer-Attikawohnung an der Z._strasse in Q._ mit Keller und zwei unterirdischen Autoeinstellplätzen "gemäss Projektplänen (Baubewilligung vom 21. Februar 2006) und gemäss separat unterzeichnetem Baubeschrieb fertig zu erstellen" und den Käufern auf den Antrittstermin schlüsselfertig und bezugsbereit zur Verfügung zu stellen. Der Kaufpreis betrug insgesamt Fr. 750'000.--. Für die fachgemässe, dem Baubeschrieb sowie den Plänen entsprechende Ausführung leistete die Verkäuferin Garantie gemäss den Bestimmungen der SIA-Norm 118 für die Dauer von zwei Jahren ab Übergabetermin bzw. ein Jahr nach Lieferung der Maschinen und Apparate gemäss den mit den Unternehmern und Lieferanten vereinbarten Bedingungen. Die Wohnung konnte am 1. Oktober 2007 übernommen werden. B. Mit Klage vom 27. November 2008 beantragten die Käufer dem Bezirksgericht Brugg, die Verkäuferin zu verpflichten, ihnen Fr. 758'633.75 nebst gestaffeltem Zins zu bezahlen. Damit verlangten sie die Wandelung des Kaufvertrages mit der Begründung, die Attika-Wohnung sei entgegen mündlich getroffener Abmachungen nicht durchwegs rollstuhlgängig. Das Bezirksgericht wies die Klage mit Urteil vom 22. Februar 2011 ab. Die Käufer legten dagegen Berufung ein mit den Anträgen, das angefochtene Urteil aufzuheben und die Sache an das Bezirksgericht Brugg zu neuem Entscheid zurückzuweisen, eventuell die Verkäuferin zu verpflichten, den Käufern Fr. 75'000.-- zu bezahlen, unter Erhöhungsvorbehalt gemäss dem Beweisergebnis. Zum Eventualantrag führten die Käufer aus, sie hätten die umstrittene Wohnung im Juni 2011 verkauft, weshalb sie nur noch den Ersatz des Minderwertes verlangen könnten. Das Obergericht des Kantons Aargau wies die Berufung mit Entscheid vom 13. März 2012 ab. C. Mit Beschwerde in Zivilsachen beantragen die Käufer (Beschwerdeführer) dem Bundesgericht, das Urteil des Obergerichts vom 13. März 2012 aufzuheben und die Sache der Vorinstanz, eventuell dem Bezirksgericht Brugg zu neuem Entscheid zurückzuweisen. Eventuell sei die Verkäuferin (Beschwerdegegnerin) zu verpflichten, den Beschwerdeführern Fr. 75'000.-- zu bezahlen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf Vernehmlassung verzichtet.