Sachverhalt:
A. Das Ehepaar A._ und B._ (Beschwerdeführer; Käufer) und C._ (Beschwerdegegnerin; Verkäuferin), vertreten durch D._, unterzeichneten am 15. Februar 2006 einen öffentlich beurkundeten Vorvertrag. Die Parteien verpflichteten sich, auf der Amtschreiberei Region Solothurn einen Kaufvertrag für das Grundstück GB E._ Nr. 1._, Baufeld F._, zum Preis von Fr. 625'000.-- abzuschliessen. Nach Ziff. 8 des Vorvertrags verfällt bei Weigerung der Kaufspartei, den Kaufvertrag zu unterzeichnen und das unwiderrufliche Zahlungsversprechen für Fr. 565'000.-- (Fr. 625'000.-- abzüglich der Anzahlung von Fr. 60'000.--) vorzulegen, ein Betrag von Fr. 60'000.-- unter Anrechnung der geleisteten Anzahlung als Konventionalstrafe zu Gunsten der Verkaufspartei.
Mit Schreiben vom 1. Juni 2007 wurden die Beschwerdeführer zur Unterzeichnung des Kaufvertrags auf die Amtschreiberei Region Solothurn eingeladen. Die Beschwerdeführer folgten dieser Einladung nicht, sondern wandten sich mit Schreiben vom 26. Juni 2007 an die Beschwerdegegnerin und erklärten, dass sie gemäss <ref-law> den Vertrag nicht einhalten würden. Sie machten geltend, aus dem Vorvertrag gehe eindeutig hervor, dass der Zugang zur Liegenschaft nicht mit einem Fussweg, sondern mit einer Zufahrtsstrasse erschlossen werden sollte. Es sei allen Vertragsbeteiligten klar, dass sie die Bauparzelle nur mit einer Zufahrtsstrasse, welche die Erstellung und Benützung von Autoabstellplätzen ermögliche, erwerben wollten. Mit dem Entscheid des Bau- und Justizdepartements vom 8. November 2006 sei nun aber auch für das Baufeld F._ festgelegt worden, dass die Anwohnerparkierung in der Einstellhalle zu erfolgen habe und GB E._ Nr. 2._ nur ein Fussweg sei. Sie würden sich daher in einem Grundlagenirrtum gemäss <ref-law> befinden und ersuchten um Rückerstattung der geleisteten Anzahlung von Fr. 60'000.--. Die Beschwerdegegnerin verwies die Beschwerdeführer mit eingeschriebenem Brief vom 28. Juni 2007 auf Ziff. 8 des Vorvertrags, wonach der geleistete Anzahlungsbetrag von Fr. 60'000.-- zu Gunsten der Verkaufspartei verfalle, wenn sich die Käufer weigern sollten, den Kaufvertrag zu unterzeichnen. Sie setzte ihnen eine Nachfrist von vierzehn Tagen, um den Kaufvertrag zu unterschreiben. In der Folge kam der Kaufvertrag über GB E._ Nr. 1._ nicht zustande.
B. Nach einer ergebnislos verlaufenen Aussöhnungsverhandlung reichten die Beschwerdeführer am 8. Februar 2008 beim Richteramt Solothurn-Lebern Klage ein. Sie beantragten, die Beschwerdegegnerin zu verpflichten, die auf das Sperrkonto UBS Nr. 3._ geleistete Anzahlung in der Höhe von Fr. 60'000.-- zuzüglich Kapitalzins zum Urteilszeitpunkt zu Gunsten der Beschwerdeführer freizugeben. Eventualiter sei die Konventionalstrafe gemäss <ref-law> richterlich herabzusetzen. Die Beschwerdegegnerin beantragte die Abweisung der Klage und verlangte widerklageweise, die Beschwerdeführer zu verurteilen, ihr den Betrag von Fr. 60'000.-- zuzüglich 5 % Zins ab 13. Juli 2007 zu bezahlen. Der sich auf dem UBS-Konto im Zeitpunkt der Rechtskraft des Urteils befindende Betrag sei auf Anrechnung an den ihr von den Beschwerdeführern zu bezahlenden Betrag zugunsten der Beschwerdegegnerin freizugeben. Mit Urteil vom 29. Oktober 2008 wies das Amtsgericht die Klage ab (Dispositiv-Ziffer 1). Es verurteilte die Beschwerdeführer, der Beschwerdegegnerin in Gutheissung der Widerklage Fr. 60'000.-- nebst Zins zu 5 % seit 13. Juli 2007 zu bezahlen (Dispositiv-Ziffer 2). Der sich auf dem Konto Nr. 3._ bei der UBS befindende Betrag sei auf Anrechnung an den gemäss Dispositiv-Ziffer 2 von den Beschwerdeführern der Beschwerdegegnerin zu bezahlenden Betrag zugunsten der Beschwerdegegnerin freizugeben (Dispositiv-Ziffer 3).
Die Beschwerdeführer appellierten gegen das Urteil des Amtsgerichts. Sinngemäss beantragten sie dem Obergericht des Kantons Solothurn, das angefochtene Urteil aufzuheben und die Beschwerdegegnerin zu verpflichten, ihnen den Betrag von Fr. 60'000.-- inklusive Zins im Urteilszeitpunkt freizugeben. Am 29. Mai 2009 wies das Obergericht die Klage ab (Dispositiv-Ziffer 1). Es verurteilte die Beschwerdeführer, der Beschwerdegegnerin in Gutheissung der Widerklage Fr. 60'000.-- nebst Zins zu 5 % seit 13. Juni 2007 zu bezahlen (Dispositiv-Ziffer 2). Der sich im Zeitpunkt der Rechtskraft des obergerichtlichen Urteils auf dem Konto bei der UBS befindende Betrag sei auf Anrechnung an den gemäss Dispositiv-Ziffer 2 von den Beschwerdeführern der Beschwerdegegnerin zu bezahlenden Betrag zu Gunsten der Beschwerdegegnerin freizugeben (Dispositiv-Ziffer 3).
C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, das Urteil des Obergerichts vom 29. Mai 2009 aufzuheben. Die Appellation und die Klage seien gutzuheissen. Die Widerklage sei abzuweisen. Die Beschwerdegegnerin sei zu verurteilen, den Betrag von Fr. 60'000.-- auf dem Sperrkonto UBS Nr. 3._ zuzüglich Zins zum Urteilszeitpunkt zu Gunsten der Beschwerdeführer freizugeben.
Die Beschwerdegegnerin und die Vorinstanz beantragen die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 2.2; <ref-ruling> E. 3.2). Macht der Beschwerdeführer eine Verletzung des Willkürverbots von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen aufzuzeigen, inwiefern dieser offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.1; <ref-ruling> E. 3.1. S. 399).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3).
2. Diese Grundsätze lassen die Beschwerdeführer über weite Strecken ausser Acht. Sie unterbreiten dem Bundesgericht eine eigene Darstellung des Sachverhalts unter freier Ergänzung der vorinstanzlichen Feststellungen, ohne rechtsgenüglich begründete Sachverhaltsrügen zu erheben. Darauf kann nicht abgestellt werden. Mit ihren weitgehend appellatorischen Vorbringen scheinen sie zudem zu verkennen, dass das Bundesgericht keine letzte Appellationsinstanz ist, die von den Parteien mit vollkommenen Rechtsmitteln angerufen werden könnte. Auch auf diese Vorbringen ist nicht einzugehen. Ferner ist der Verweis der Beschwerdeführer auf ihre Ausführungen in ihrer kantonalen Appellationsschrift unbeachtlich, hat doch die Begründung der Beschwerde in der Eingabe selbst enthalten zu sein (vgl. <ref-ruling> E. 1d; <ref-ruling> E. 2; <ref-ruling> E. 3 S. 85; <ref-ruling> E. 4a S. 30). Zu den Vorbringen der Beschwerdeführer ist lediglich Folgendes zu bemerken:
3. Die Beschwerdeführer rügen in ihrer Beschwerdeschrift eine Verletzung von <ref-law> und eventualiter eine Verletzung von <ref-law>.
3.1 Sie bringen vor, die Beschwerdegegnerin habe ihnen mündlich und schriftlich zugesichert, dass ihr Grundstück GB E._ Nr. 1._ mit einer Zufahrtsstrasse erschlossen werde und sie demzufolge auch auf ihrem Grundstück parkieren könnten. Aufgrund des Entscheids des Bau- und Justizdepartements vom 8. November 2006 habe sich herausgestellt, dass diese ihnen zugesicherte Eigenschaft nicht vorhanden sei. Wenn ihnen die Beschwerdegegnerin nicht versprochen hätte, dass die Zufahrtsstrasse gebaut werden würde und sie ihre Autos in einem Carport auf ihrem Grundstück parkieren könnten, hätten sie sich nie für dieses Stück Land interessiert. Sie hätten den Vorvertrag nicht unterzeichnet, wenn die Beschwerdegegnerin die Zufahrtsstrasse im Vorvertrag nicht schriftlich zugesichert hätte.
3.2 Die Vorinstanz ist nach einer Würdigung des Vorvertrags vom 15. Februar 2006, des Gestaltungsplans und der Sonderbauvorschriften sowie den Aussagen des Zeugen D._ zum Schluss gekommen, es sei den Beschwerdeführern nicht gelungen, glaubhaft darzulegen, dass für sie die Zufahrts- sowie die Parkmöglichkeit auf dem Grundstück ein wesentlicher Vertragsbestandteil gewesen sei. Weder im Vorvertrag noch im integrierenden Gestaltungsplan mit den dazugehörenden Sonderbauvorschriften seien irgendwelche diesbezüglichen Zusicherungen gemacht worden. Zudem habe es den Beschwerdeführern als vorsichtige Käufer und Bauherren klar sein müssen, dass ein vom Regierungsrat genehmigter Gestaltungsplan nur von der Genehmigungsbehörde selbst, also wiederum vom Regierungsrat, abgeändert oder aufgehoben werden könne. Allfällige von der Gemeinde, dem Architekten oder von sonst wem gemachte Versprechungen hätten lediglich als mögliche zu prüfende Optionen verstanden werden dürfen, sicher aber nicht als den Gestaltungsplan abänderbare Entscheidungen. Da in den Sonderbauvorschriften klar festgehalten worden sei, dass bezüglich der Art und Zahl der ober- und unterirdischen Autoabstellplätze das Baubewilligungsverfahren massgebend sei, könnten die Beschwerdeführer nicht ernsthaft behaupten, ihnen seien verbindliche mündliche Zusagen irgendwelcher Art gemacht worden. Wäre die mögliche Zufahrt zum Grundstück sowie die Parkmöglichkeit auf dem Grundstück derart wichtig gewesen, wäre dies mit Sicherheit in den sehr ausführlich geregelten Vorvertrag aufgenommen worden. Schliesslich seien die Beschwerdeführer auf <ref-law> hinzuweisen. Einen allenfalls bestehenden Irrtum hätten die Beschwerdeführer ihrer eigenen Fahrlässigkeit zuzuschreiben. Die Beschwerdegegnerin könnten sie jedenfalls nicht dafür behaften, zumal der Zeuge ausdrücklich ausgeführt habe, die Strasse und die Parkmöglichkeiten seien nie ein Thema gewesen.
3.3 Die Beschwerdeführer setzen sich mit diesen vorinstanzlichen Erwägungen nicht rechtsgenüglich auseinander. Sie zeigen insbesondere nicht auf, inwiefern die Vorinstanz willkürlich zu ihrer Schlussfolgerung gekommen wäre, dass keine Zusicherung seitens der Beschwerdegegnerin bezüglich einer Zufahrts- und Parkmöglichkeit vorgelegen habe. Soweit die Beschwerdeführer ausführen, die Vorinstanz hätte ihre Begründung und Beweismittel ignoriert, so namentlich die Ziffern 5, 12 und 13 des Vorvertrags, verkennen sie, dass die Vorinstanz diese Vertragsziffern sehr wohl berücksichtigte. Wie aus der Erwägung 2 des angefochtenen Entscheids hervorgeht, hat sich die Vorinstanz ausdrücklich mit den erwähnten Bestimmungen beschäftigt. In Würdigung derselben ist sie jedoch zu einem anderen Schluss gekommen als die Beschwerdeführer. Inwiefern die Sachverhaltsfeststellung der Vorinstanz offensichtlich unrichtig wäre, legen die Beschwerdeführer nicht dar. Sie schildern lediglich ausführlich ihre eigene Auffassung der Dinge. Damit vermögen sie den Anforderungen an eine Sachverhaltsrüge nicht zu genügen (vgl. Erwägung 1).
Somit bleibt es beim vorinstanzlich festgestellten Sachverhalt. Es steht demzufolge in tatsächlicher Hinsicht fest, dass die Beschwerdegegnerin den Beschwerdeführern weder eine Zufahrtsmöglichkeit zu ihrem Grundstück noch eine Parkmöglichkeit auf ihrem Grundstück zusicherte. Die Beschwerdeführer haben zudem nicht beweisen können, dass sie den Vorvertrag ohne die Möglichkeit, über eine Zufahrtsstrasse mit ihren Autos auf ihr Grundstück zu gelangen und die Fahrzeuge auf ihrem Grundstück abzustellen, nicht abgeschlossen hätten. Ein Grundlagenirrtum liegt somit nicht vor, und eine Verletzung von <ref-law>, die im Übrigen von den Beschwerdeführern nicht näher begründet wird, scheidet aus.
3.4 Inwiefern schliesslich die <ref-law> verletzt wären, tun die Beschwerdeführer ebenso nicht näher dar und ist nicht ersichtlich. Nach Ziff. 9 des Vorvertrags haben die Parteien jede kaufrechtliche Gewährleistungspflicht der Verkaufspartei für rechtliche und körperliche Mängel am Grundstück, soweit gesetzlich zulässig, ausdrücklich aufgehoben, unter Vorbehalt allfälliger im Kaufvertrag enthaltener oder sonst der Kaufspartei schriftlich abgegebener Zusicherungen der Verkaufspartei. Nach dem vorinstanzlich festgestellten Sachverhalt hat die Beschwerdegegnerin den Beschwerdeführern gerade keine Zusicherung betreffend eine Zufahrtsstrasse und Möglichkeit, das Auto auf dem Grundstück abzustellen, abgegeben. Somit vermögen die Beschwerdeführer auch aus der entsprechenden Vertragsziffer nichts zu ihren Gunsten abzuleiten.
4. Der Vollständigkeit halber sei erwähnt, dass die Beschwerdeführer vor Bundesgericht (wie bereits vor Obergericht) eine allfällige Herabsetzung der Konventionalstrafe nicht mehr verlangen. Sie tun nicht dar, dass die Konventionalstrafe übermässig hoch wäre und Herabsetzungsgründe vorliegen würden. Eine Herabsetzung fällt somit ausser Betracht, da die Voraussetzungen einer solchen von den Beschwerdeführern als Schuldner zu behaupten und zu beweisen wären (<ref-ruling> E. 4.1 S. 53 f., 201 E. 5.2 S. 210; <ref-ruling> E. 1b).
5. Aus diesen Gründen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 5. Januar 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Sommer