Sachverhalt:
A. A. und B. X._ (Beschwerdeführer) waren seit 1996 Mieter in der Liegenschaft Z._strasse in M._. Am 8. Juli 2003 schlossen die Schwestern C. Q._ und D._ als Vermieterinnen mit den Beschwerdeführern einen neuen Mietvertrag über Geschäftsräumlichkeiten in dieser Liegenschaft für die Nutzung als Gastronomiebetriebe. Nach Abschluss des Vertrags verstarb D._, deren einzige Erbin ihre Schwester C. Q._ war.
Als Folge eines Unfalls war der Beschwerdeführer 1 nicht mehr in der Lage, seinen Beruf als Wirt auszuüben. Deshalb hat er die Mieträumlichkeiten an der Z._strasse ab 1. Januar 2002 (Restaurant) und ab 1. Juni 2004 (Bar) je für die Dauer von sechs Jahren und ab 1. Januar 2004 (Cafeteria) für ein Jahr untervermietet.
Mit Kaufvertrag vom 29. Juli 2004 verkauften die Beschwerdeführer C. Q._ und deren Ehemann E. Q._ die Inneneinrichtungen inklusive die Maschinen, Geräte und das Mobiliar sowie die Untermietverträge und einen Getränkelieferungsvertrag zum Preis von Fr. 750'000.--. Am 19. August 2004 überwies E. Q._ den Beschwerdeführern Fr. 150'000.--. Er starb am 20. November 2004.
Am 18. November 2008 kündigte die Verwaltung der betreffenden Liegenschaft das Mietverhältnis mit den Beschwerdeführern wegen Zahlungsverzugs per 31. Dezember 2008. Diese fochten die Kündigung an. Am 24. August 2010 wies das Obergericht des Kantons Zürich die Klage ab und stellte fest, dass die Kündigungen vom 18. November 2008 der Mietverträge für Restaurant etc. im EG und für die 3-Zimmerwohnung im 3. OG an der Z._strasse in M._ rechtsgültig sind. Mit Urteil vom 17. Februar 2011 wies das Bundesgericht die dagegen von den Beschwerdeführern erhobene Beschwerde in Zivilsachen ab, soweit es darauf eintrat (Verfahren 4A_549/2010).
B. Am 16. September 2005 klagten die Beschwerdeführer gegen C. Q._ beim Bezirksgericht Zürich. Sie verlangten die Bezahlung des noch offenen Kaufpreises gemäss dem Vertrag vom 29. Juli 2004 in Höhe von Fr. 600'000.-- nebst Zins zu 5 % seit dem 29. Juli 2004, eventualiter Zug um Zug gegen Übertragung der Kaufgegenstände sowie gegen Abtretung bzw. Übertragung der bestehenden Untermietverträge und des bestehenden Getränkelieferungsvertrags inkl. des damit verbundenen Darlehensvertrags. Das Bezirksgericht wies die Klage am 16. September 2009 ab.
Dagegen erklärten die Beschwerdeführer Berufung an das Obergericht des Kantons Zürich mit gleichlautenden Anträgen. Die Beklagte C. Q._ starb am 15. März 2010. In ihrem Testament setzte sie die Y._ AG (Beschwerdegegnerin) als Willensvollstreckerin ein. Mit Beschluss vom 17. Juni 2010 wurde vorgemerkt, dass neu die Willensvollstreckerin als Beklagte in den Prozess eingetreten ist. Am 24. März 2011 wies das Obergericht die Klage ebenfalls ab.
C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, das Urteil des Obergerichts vom 24. März 2011 sei aufzuheben. Die Beschwerdegegnerin sei zu verpflichten, den Beschwerdeführern Fr. 600'000.-- nebst Zins zu 5 % seit dem 29. Juli 2004 zu bezahlen. Eventualiter sei die Beschwerdegegnerin zu verpflichten, den Beschwerdeführern Fr. 600'000.-- nebst Zins zu 5 % seit dem 29. Juli 2004 zu bezahlen, und zwar Zug um Zug gegen Übertragung der Kaufgegenstände (Einrichtung des Restaurants Taverna N._, der Taverna Bar N._ und der Cafeteria N._ an der O._strasse/Z._strasse in M._) gemäss den drei Schätzungsberichten der P._-consult AG je vom 4. Februar 2003 sowie gegen Abtretung bzw. Übertragung der bestehenden Untermietverträge für das Restaurant und die Cafeteria sowie des bestehenden Getränkelieferungsvertrags vom 26. Juni 2003 inkl. des damit verbundenen Darlehensvertrags mit der R._ Getränke AG an die Beschwerdegegnerin gemäss dem Kaufvertrag zwischen B. und A. X._ und "C. Q._ & "E. Q._ vom 29. Juli 2004. Eventualiter sei die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Mit Verfügung vom 16. Juni 2011 wurde das Gesuch der Beschwerdeführer um Bewilligung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren abgewiesen. In der Folge überwiesen die Beschwerdeführer den verlangten Kostenvorschuss.
Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Die Vorinstanz stützte die Abweisung der Klage auf eine Doppelbegründung. In einer ersten Begründung erachtete sie den Kaufvertrag als nichtig, weil sie es für erwiesen hielt, dass E. Q._ diesen Vertrag im Zustand der Urteilsunfähigkeit (zufolge Demenz) unterzeichnet habe. Die Gegenbeweismittel der Beschwerdeführer vermochten diesen Schluss nicht zu widerlegen und konnten auch kein luzides Intervall für den fraglichen Zeitpunkt nachweisen. Die Vorinstanz hielt es ferner für erwiesen, dass C. Q._ den Vertrag ohne Mitwirkung ihres Ehemannes nicht geschlossen hätte. Damit habe der Nachweis der Urteilsunfähigkeit des Ehemannes bei Vertragsschluss die Nichtigkeit des Vertrags auch gegenüber C. Q._ zur Folge. Da der Kaufvertrag vom 29. Juli 2004 nichtig sei, sei der Klageforderung die Grundlage entzogen und die Klage abzuweisen.
In einer zweiten selbständigen Begründung erwog die Vorinstanz, die Klage sei auch aus einem anderen Grund abzuweisen: Der Vertrag sei wegen Nichteintritts einer in Ziffer 6 des Vertrags vorgesehenen Bedingung nicht zustande gekommen, die wie folgt lautet:
"Es wird vereinbart, dass dieser Kaufpreis sofort nach Unterzeichnung dieses Kaufvertrags auf das Konto von B. & A. X._ bei der Bank S._, Konto-Nr. xxx._ einbezahlt wird. Der Kaufvertrag wird demnach mit dem Zahlungseingang rechtskräftig und die Verkäufer verpflichten sich, die notwendigen Übertragungen der verschiedenen Verträge vorzunehmen."
Die Vorinstanz hielt den Beweis für den von den Beschwerdeführern behaupteten übereinstimmenden Parteiwillen für nicht erbracht, dass mit dieser Vertragsbestimmung nur eine Vorleistungspflicht bezüglich des Kaufpreises, aber keine Bedingung für das Zustandekommen des Vertrages vereinbart worden sei. Sie legte die Bestimmung daher nach dem Vertrauensprinzip aus, wobei sie erwog, Ziffer 6 des Vertrags sei so zu verstehen, dass erst die Zahlung des Kaufpreises den Vertrag "rechtskräftig", d.h. verbindlich mache. Dies könne nur den Sinn haben, dass das verbindliche Einverständnis erst mit der Zahlung des vollen Kaufpreises erfolgen sollte. Mithin sei die Zahlung eine Bedingung für das Entstehen des Vertrags gewesen. Da diese Bedingung nicht eingetreten sei, sei der Kaufvertrag nicht rechtsgültig zustande gekommen. Mithin fehle es auch deswegen an einer rechtlichen Grundlage für den klägerischen Anspruch, was ebenfalls dazu führe, dass die Klage abzuweisen sei.
1.2 Beruht der angefochtene Entscheid auf mehreren selbständigen Begründungen, die je für sich den Ausgang des Rechtsstreits besiegeln, so hat der Beschwerdeführer darzulegen, dass jede von ihnen Recht verletzt; andernfalls kann auf die Beschwerde nicht eingetreten werden (<ref-ruling> E. 6.3; vgl. auch <ref-ruling> E. 2.2 S. 535 f.).
1.3 Der vorliegenden Beschwerde ist eine rechtsgenügliche Anfechtung der zweiten Begründung kaum zu entnehmen. Dies stellt bereits das Eintreten auf die Beschwerde in Frage.
Ohnehin wären aber die Vorbringen gegen die zweite Urteilsmotivation als unbegründet abzuweisen. Die Beschwerdeführer tragen diesbezüglich vor, selbst wenn davon ausgegangen werde, dass Ziffer 6 des Kaufvertrags eine Resolutivbedingung enthalte (bestritten), hätten die Parteien in der Folge auf die Geltendmachung dieser Bedingung verzichtet, indem die Käufer am 19. August 2004 eine Tranche im Betrag von Fr. 150'000.-- an die Beschwerdeführer überwiesen und diese die Zahlung angenommen sowie hierauf die Übertragung der Kaufgegenstände mehrfach angeboten hätten. Mit letzterer Behauptung erweitern die Beschwerdeführer den für das Bundesgericht verbindlich festgestellten Sachverhalt (Art. 105 Abs. 1 BGG) in unzulässiger Weise (vgl. <ref-ruling> E. 1.5; <ref-ruling> E. 1.4.3; <ref-ruling> E. 7.1), hat die Vorinstanz doch nicht festgestellt, dass die Beschwerdeführer die Übertragung der Kaufgegenstände nach der Zahlung des Betrags von Fr. 150'000.-- mehrfach angeboten hätten. Darauf kann nicht abgestellt werden. Die Teilzahlung von Fr. 150'000.-- hat die Vorinstanz im Rahmen der Prüfung des von den Beschwerdeführern behaupteten tatsächlichen Parteiwillens berücksichtigt und zu Recht als blossen Beleg für eine Zahlungsabsicht bzw. einen Zahlungswillen gewürdigt. Allein aus dieser Teilzahlung kann jedoch nicht abgeleitet werden, die Parteien hätten auf die Bedingung nach Ziffer 6 des Kaufvertrags verzichtet. Für die Annahme eines solchen Verzichts fehlen schlüssige Anhaltspunkte und das entsprechende Tatsachenfundament.
Auch vermögen die Beschwerdeführer die Auslegung der Vorinstanz nicht als bundesrechtswidrig auszuweisen, indem sie ihr lediglich die Behauptung entgegensetzen, Ziffer 6 sei allein deshalb in den Vertrag aufgenommen worden, um die Beschwerdeführer davor zu schützen, den Kaufgegenstand auf die Käuferschaft übertragen zu müssen, bevor eine (Teil-)Zahlung erfolgt sei. Sie erneuern damit lediglich ihre Ansicht, gemäss übereinstimmendem tatsächlichen Willen der Vertragsparteien habe Ziffer 6 des Vertrags eine Vorleistungspflicht der Käufer beinhalten sollen. Laut Vorinstanz misslang den Beschwerdeführern der Beweis für einen solchen übereinstimmenden Parteiwillen, was eine Auslegung nach dem Vertrauensprinzip notwendig machte. Inwiefern die Vorinstanz dabei Bundesrecht verletzt haben sollte, begründen die Beschwerdeführer nicht und ist nicht ersichtlich.
1.4 Die zweite Begründung des angefochtenen Entscheids hält demnach der bundesgerichtlichen Überprüfung stand. Sie vermag die Klageabweisung allein zu stützen. Damit erübrigt es sich, auf die Kritik der Beschwerdeführer gegen die erste Begründung der Vorinstanz einzugehen.
2. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 und 5 BGG). Mangels Einholung einer Beschwerdeantwort erwuchs der Beschwerdegegnerin für das bundesgerichtliche Verfahren kein Aufwand, weshalb ihr keine Parteientschädigung zuzusprechen ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 8'500.-- werden den Beschwerdeführern auferlegt, in solidarischer Haftbarkeit.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 3. August 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Widmer