Sachverhalt: A. In der Zeit vom November/Dezember 2005 (Baubeginn) bis 10. März 2010 (Bauabnahme/Baukontrolle) liess der damalige Eigentümer A._ auf seinen Parzellen Nr. 1241 und 1308 in B._ ein Mehrfamilienhaus mit Unterniveaugarage erstellen. Bei den Aushubarbeiten ereignete sich am 17./19. Dezember 2005 eine Rutschung in der Baugrubenböschung längs der Parzellengrenze zur Liegenschaft C._strasse 4 in B._, welche im Eigentum von X._ und Y._ steht, und führte zu Beschädigungen an ihrem Wohnhaus. Am 21. April 2010 erstatteten X._ und Y._ Strafanzeige gegen A._ sowie gegen weitere Beteiligte (Mittäter, Anstifter, Gehilfen) wegen des Verdachts der Sachbeschädigung, der Gefährdung durch Verletzung der Regeln der Baukunde und allenfalls weiterer Delikte. Sie machten geltend, sowohl der Unternehmer als auch der Bauleiter seien beim Aushub auf die Rutschgefahr, welche allgemein bekannt gewesen sei, aufmerksam gemacht worden. Die Bodenverschiebungen und die daraus resultierenden Beschädigungen an ihrer Liegenschaft seien wahrscheinlich darauf zurückzuführen, dass der Bauherr aus Kostengründen darauf verzichtet habe, die Baugrube fachgemäss zu sichern und Anker einzubauen. Die Staatsanwaltschaft des Kantons Solothurn eröffnete am 10. Mai 2010 eine Strafuntersuchung gegen A._ sowie gegen evtl. unbekannte Täterschaft wegen Sachbeschädigung, evtl. Anstiftung zu Sachbeschädigung, vorsätzliche Gefährdung durch Verletzung der Regeln der Baukunde resp. evtl. fahrlässiger Gefährdung durch Verletzung der Regeln der Baukunde. Sie beauftragte die Polizei mit weiteren Ermittlungen (u.a. Einvernahmen der Geschädigten und der beschuldigten Person, Befragung von Auskunftspersonen). Mit Eingabe vom 30. Mai 2011 teilten X._ und Y._ der Staatsanwaltschaft mit, dass sie sich als Zivilkläger am Strafverfahren beteiligten und machten Schadenersatz in der Höhe von Fr. 500'000.-- sowie Genugtuung in der Höhe von Fr. 30'000.-- geltend. Am 6. Juli 2011 erteilte die Staatsanwaltschaft D._, dipl. Ing ETH, den Auftrag, ein baukundliches Gutachten zu erstellen. Nach Eingang des Gutachtens wurden A._ sowie X._ und Y._ durch die Staatsanwaltschaft zur Stellungnahme dazu aufgefordert. A._ liess mit Eingabe vom 13. September 2011 mitteilen, dass er auf eine Stellungnahme verzichte. X._ und Y._ erklärten am 13. September 2011, dass nach hiesiger Kenntnis eine Ergänzung des Gutachtens von D._ nicht erforderlich sei. Am 19. September 2011 teilte die Staatsanwaltschaft den Parteien mit, sie halte die Strafuntersuchung für vollständig. Es sei beabsichtigt, die Verfahren einzustellen; die Parteien hätten zuvor Gelegenheit, Einsicht in die Akten zu nehmen und Beweisergänzungsbegehren zu stellen. Der Vertreter von A._ liess eine Kostennote zukommen. X._ und Y._ liessen sich nicht vernehmen. B. Mit Verfügung vom 11. Oktober 2011 stellte die Staatsanwaltschaft die Strafuntersuchung gegen A._ wegen Sachbeschädigung, evtl. Anstiftung zu Sachbeschädigung, vorsätzlicher Gefährdung durch Verletzung der Regeln der Baukunde resp. evtl. fahrlässiger Gefährdung durch Verletzung der Regeln der Baukunde ein. Zur Begründung wurde im Wesentlichen erwogen, der Umstand, dass in Anbetracht der bestehenden Risiken keinerlei Massnahmen erwogen resp. ergriffen worden seien, stelle einen Verstoss gegen die Regeln der Baukunst dar. Strafbar sei jedoch nur die vorsätzliche Sachbeschädigung; ein vorsätzliches Handeln könne dem Beschuldigten nicht nachgewiesen werden. Vorliegend habe das fehlerhafte Verhalten des Beschuldigten nicht zu einer Gefährdung von Menschen geführt, weshalb die Anwendung von Art. 229 StGB entfalle. C. Gegen die Einstellungsverfügung reichten X._ und Y._ am 27. Oktober 2011 Beschwerde beim Obergericht des Kantons Solothurn ein. Sie beantragten deren Aufhebung sowie die Anweisung der Staatsanwaltschaft, das Verfahren fortzusetzen. Mit Entscheid vom 29. Februar 2012 wies das Obergericht des Kantons Solothurn, Beschwerdekammer, die Beschwerde ab. D. Dagegen gelangten X._ und Y._ mit Beschwerde vom 27. März 2012 an das Bundesgericht. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Staatsanwaltschaft anzuweisen, das Strafverfahren gegen den Beschuldigten wieder aufzunehmen und fortzusetzen. Eventuell sei die Sache zu neuer Entscheidung an die Vorinstanz oder an die Staatsanwaltschaft zurückzuweisen. E. Die Vorinstanz verzichtet auf eine Stellungnahme und beantragt, die Beschwerde abzuweisen. Die Staatsanwaltschaft schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten ist. Der Beschwerdegegner beantragt die Abweisung der Beschwerde. Die Beschwerdeführer halten in ihrer Replik an ihren Anträgen fest. 