Sachverhalt: A. A.a. X._ (1982) und Y._ (1973) sind die unverheirateten Eltern von A._ (geb. 2012). X._ ist ausserdem Mutter von B._ (2007) und C._ (2010). A.b. Kurz nach der Geburt von A._, am 5. Dezember 2012, wurden die Beschwerdeführer durch Intervention des Psychiatrischen Dienstes des Spitals Z._ in die Privatklinik D._ (X._) resp. in das Psychiatriezentrum E._ (Y._) eingewiesen. Mit superprovisorischem Entscheid der Kindes- und Erwachsenenschutzbehörde Z._ (KESB), ebenfalls vom 5. Dezember 2012, entzog die KESB X._ die Obhut über A._ und brachte das Kind bis auf weiteres in der Geburtenabteilung des Spitals Z._ unter. Am 7. Dezember 2012 wurde A._ zur Mutter in die Privatklinik D._ verbracht, welche über einen Mutter-Kind-Platz verfügt. Die Vaterschaft von Y._ war zu diesem Zeitpunkt noch nicht rechtsgültig erstellt. A.c. Mit Entscheid vom 10. Dezember 2012 bestätigte die KESB den am 5. Dezember 2012 superprovisorisch ausgesprochenen Obhutsentzug und wandelte diesen in eine vorsorgliche Massnahme für die Dauer des Verfahrens um. Gleichzeitig bestätigte die KESB formell die Umplatzierung von A._ in den Mutter-Kind-Platz der Klinik D._. B. B.a. Am 22. Januar 2013 teilte die Privatklinik D._ der KESB mit, dass X._ per 31. Januar 2013 entlassen werde, da sich die Situation zugespitzt habe und kaum mehr tragbar sei. Am 29. Januar 2013 fand ein Eintrittsgespräch in der Klinik F._ statt, welche ebenfalls über Mutter-Kind-Plätze verfügt. Am 31. Januar 2013 teilte die Klinik mit, dass die Aufnahme von X._ und der Tochter nicht möglich sei. B.b. Daraufhin brachte die KESB A._ mit superprovisorischem Entscheid vom 31. Januar 2013 für die Dauer des Verfahrens im Kinderheim G._ in E._ unter. Die KESB entzog einer allfälligen Beschwerde die aufschiebende Wirkung. B.c. Die in diesem Stadium anwaltlich vertretenen X._ und Y._ erhoben am 8. Februar 2013 gegen diesen Entscheid Beschwerde an das Obergericht des Kantons Bern. Sie beantragten, die Platzierung von A._ im Kinderheim sei aufzuheben und die Obhut sei ihnen zurückzugeben. Ausserdem sei die aufschiebende Wirkung zu gewähren. Die zuständige Instruktionsrichterin des Obergerichts wies das Gesuch um aufschiebende Wirkung am 13. Februar 2013 ab. C. C.a. Mit Entscheid vom 19. Februar 2013 bestätigte die KESB ihren superprovisorischen Entscheid vom 31. Januar 2013 im Sinne einer vorsorglichen Massnahme bis zum rechtskräftigen Entscheid. Einer allfälligen Beschwerde entzog die KESB wiederum die aufschiebende Wirkung. C.b. Am 4. März 2013 liessen die Beschwerdeführer auch gegen diesen Entscheid Beschwerde an das Obergericht des Kantons Bern führen. Sie beantragten, die Platzierung von A._ im Kinderheim sei aufzuheben und die Obhut sei ihnen zurückzugeben. Weiter ersuchten sie um Gewährung der aufschiebenden Wirkung und um Vereinigung der beiden Beschwerdeverfahren. Die Instruktionsrichterin des Obergerichts vereinigte die Verfahren mit Verfügung vom 12. März 2013. Die KESB schloss in beiden Beschwerdeverfahren auf Abweisung. C.c. Mit Verfügung vom 13. März 2013 beauftragte die KESB nach vorheriger Vernehmlassung der Parteien Frau Dr. phil. H._, Kantonale Erziehungsberatung Interlaken, mit der Erstellung eines Fachgutachtens bis am 31. Juli 2013. Am 14. März 2013 reichten die Beschwerdeführer einen Beleg betreffend Vaterschaftsanerkennung nach. D. D.a. Mit Entscheid vom 19. April 2013 wies das Kindes- und Erwachsenenschutzgericht des Obergerichts des Kantons Bern (Vorinstanz) die Beschwerden ab. Gleichzeitig hielt das Gericht fest, dass trotz angeordneter Unterbringung Hand geboten würde, falls die Beschwerdeführer eine geeignete Mutter-Kind-Institution vorschlagen, welche eine 24-Stunden-Betreuung anbiete und bereit sei, die Beschwerdeführerin zusammen mit der Tochter für die Dauer der Begutachtung aufzunehmen. D.b. Am 22. April 2013 (Postaufgabe 23. April 2013) erhoben X._ und Y._, die nicht mehr anwaltlich vertreten werden, Beschwerde an das Bundesgericht. Mit Schreiben vom 27. April 2013 (Postaufgabe 29. April 2013) nahmen die Beschwerdeführer unaufgefordert ein zweites Mal Stellung und reichten eine verfahrensleitende Verfügung der KESB vom 26. April 2013 betreffend die entfallene anwaltliche Vertretung ein. Die Vorinstanz verzichtete mit Postaufgabe vom 22. Mai 2013 auf eine Vernehmlassung. Sie verwies auf den angefochtenen Entscheid und die Akten. E. E.a. Am 21. Mai 2013 ging beim Bundesgericht ausserdem die Kopie eines Kammerentscheides der KESB vom 17. Mai 2013 ein, woraus hervorgeht, dass den Parteien für die weitere Dauer des (kantonalen) Verfahrens vorsorglich das Besuchsrecht für das Kind A._, entzogen bzw. verweigert wurde. E.b. Die beiden Söhne C._ und B._ leben gegenwärtig ebenfalls nicht bei der Mutter. Die Obhut wurde ihr erstmals 2010 entzogen. Im März 2012 wurden die Söhne wieder der Mutter anvertraut, bevor am 17. Oktober 2012 erneut ein Obhutsentzug erfolgte. Gleichzeitig wurde ein Case Management für Kinder psychisch kranker Eltern durch das Institut für Forensik und Rechtspsychologie/Fachstelle für Kindes- und Erwachsenenschutz Bern (IFB) angeordnet. Die Söhne wurden bei deren Vater K._ platziert. Diesbezüglich ist ein separates Verfahren vor der Vorinstanz hängig. F. Gegenwärtig sind die Beschwerdeführerin im Psychiatriezentrum E._ und der Beschwerdeführer in der Privatklinik D._ untergebracht. 