Sachverhalt: A. A.a. A.A._ und B.A._ sind die Eltern der Kinder C.A._ (geb. 2003), D.A._ (geb. 2007) und E.A._ (geb. 2013). Ab Juni 2011 bestand für die Familie A._ eine Familienbegleitung, die durch das Sozialatelier F._, durchgeführt wurde. Für C.A._ und D.A._ wurde am 22. Februar 2011 je eine Beistandschaft errichtet, für E.A._ geschah dies am 22. August 2013. Am 5. März 2013 erstattete die Beiständin der Kindes- und Erwachsenenschutzbehörde U._ (KESB) eine Gefährdungsmeldung und beantragte, den Kindseltern seien umgehend und längerfristig Auflagen bezüglich Ordnung in der Wohnung und Hygiene sowie Zusammenarbeit mit der Schule und dem Erarbeiten von Erziehungs- und Förderungskompetenzen zu machen und diese entsprechend zu überprüfen oder überprüfen zu lassen. Mit Entscheid der KESB vom 21. Mai 2013 wurde die bestehende Familienbegleitung um ein halbes Jahr verlängert und den Kindseltern die Weisung erteilt, mit der Beiständin und der Familienbegleiterin zusammenzuarbeiten. Gestützt auf den Bericht des Sozialateliers F._ vom 23. Mai 2013 beantragte die Beiständin am 19. Juli 2013, die klassische sozialpädagogische Familienbegleitung durch eine familienergänzende sozialpädagogische Betreuung der Kinder bei den Eltern zuhause zu ersetzen. Anfang August 2013 gab die KESB beim Kinder- und Jugendpsychiatrischen Dienst des Kantons Solothurn (KJPD) ein Gutachten in Auftrag, welches am 21./29. November 2013 erstattet wurde (Teilgutachten über die Erziehungsfähigkeit der Kindseltern/Kinderschutzgutachten). Mit Entscheid vom 18. Dezember 2013 entsprach die KESB dem Antrag der Beiständin. Am 27. März 2014 erstattete die Beiständin einen Zwischenbericht und ersuchte die KESB, sie mit der Suche nach einer geeigneten Lösung im Falle einer Fremdplatzierung zu beauftragen. A.b. Mit Entscheid vom 17. Dezember 2014 entzog die KESB den Eltern die Obhut über die drei Kinder und platzierte diese bei einer Pflegefamilie. Einer allfälligen Beschwerde gegen diesen Entscheid wurde die aufschiebende Wirkung entzogen. A.c. Gegen diesen Entscheid der KESB erhoben die Eltern am 19. Januar 2015 Beschwerde beim Verwaltungsgericht des Kantons Solothurn mit den Anträgen, den Entscheid der KESB vom 17. Dezember 2014 vollumfänglich aufzuheben, anstelle des Entzugs der Obhut die bisherige Erziehungsbeistandschaft sowie die sozialpädagogische Familien- und Wohnbegleitung und Betreuung beizubehalten oder allenfalls anzupassen resp. mit ergänzenden ambulanten Massnahmen zu erweitern. Ferner sei ein gerichtliches Gutachten zur Erziehungsfähigkeit der Eltern einzuholen. Des weiteren ersuchten sie darum, der Beschwerde aufschiebende Wirkung zu erteilen. Mit Verfügung vom 28. Januar 2015 wies der Instruktionsrichter des Verwaltungsgerichts das Gesuch um Wiederherstellung der aufschiebenden Wirkung ab. Auf die gegen diese Verfügung erhobene Beschwerde trat das Bundesgericht nicht ein (Urteil 5A_120/2015 vom 31. März 2015). In der Sache wies das Verwaltungsgericht mit Urteil vom 27. Juli 2015 die Beschwerde ab. B. B.a. Mit Beschwerde in Zivilsachen vom 14. September 2015 wenden sich A.A._ und B.A._ (Beschwerdeführer) an das Bundesgericht. Sie verlangen, die Sache zur Durchführung einer öffentlichen Verhandlung resp. einer persönlichen Anhörung der Beschwerdeführer vor dem Gesamtgericht nach Art. 6 Ziff. 1 EMRK sowie zur Kinderanhörung an die Vorinstanz zurückzuweisen. Während dieser Zeit seien die Kinder in die elterliche Wohnung rückzuplatzieren. Eventualiter sei festzustellen, dass die Voraussetzungen für die Aufhebung des Aufenthaltsbestimmungsrechts verknüpft mit der Fremdplatzierung nicht erfüllt seien und entsprechend sei der elterliche Obhutsentzug aufzuheben und eine Rückplatzierung in die elterliche Wohnung anzuordnen. Anstelle des Entzugs der elterlichen Obhut seien eine Erziehungsbeistandschaft und eine sozialpädagogische Familien- und Wohnbegleitung anzuordnen. Subeventualiter sei die Beschwerdesache zur Durchführung weiterer Abklärungsmassnahmen, insbesondere zur Einholung eines Gerichtsgutachtens zur Beurteilung der Erziehungsfähigkeit der Beschwerdeführer an die Vorinstanz zurückzuweisen. Die Beschwerdeführer verlangen zudem die Gewährung der unentgeltlichen Rechtspflege. B.b. Das ebenfalls in der Beschwerde gestellte Gesuch um aufschiebende Wirkung wies das Bundesgericht am 16. September 2015 ab, weil die Beschwerdeführer keine die aufschiebende Wirkung rechtfertigenden Gründe vorgebracht haben. C. Das Verwaltungsgericht beantragt in seiner Vernehmlassung vom 19. November 2015, die Beschwerde kostenfällig abzuweisen. Auf den Inhalt der Vernehmlassung wird in den Erwägungen eingegangen. Die KESB liess sich nicht vernehmen. Die Vernehmlassung des Verwaltungsgerichts wurde den Beschwerdeführern zur Wahrung des rechtlichen Gehörs zur Kenntnis gebracht. Diese haben mit Eingabe vom 17. Dezember 2015 erneut Stellung genommen und einen zweiten Schriftenwechsel verlangt. Diesem Anliegen hat der Instruktionsrichter nicht entsprochen, die Stellungnahme der Beschwerdeführer aber der Vorinstanz und der KESB zur Kenntnis gebracht. Die KESB stellte dem Bundesgericht schliesslich eine Kopie des Entscheides vom 16. Dezember 2015 betreffend Zustimmung zu einer Reise mit den Pflegeeltern zu. D. Die Beschwerde wurde an der Sitzung der II. zivilrechtlichen Abteilung des Bundesgerichts vom 2. Juni 2016 öffentlich beraten und das Urteil anschliessend an die Beratung und Abstimmung mündlich eröffnet.