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.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (<ref-law>) betreffend die vorsorgliche Anordnung von Kindesschutzmassnahmen (<ref-law>). Es handelt sich um einen selbständig eröffneten Zwischenentscheid, der einen nicht wieder gutzumachenden Nachteil zur Folge haben kann (<ref-law>; <ref-ruling> E. 1 S. 477). Bei Zwischenentscheiden folgt der Rechtsweg jenem der Hauptsache (<ref-ruling> E. 1.1 S. 382). In dieser geht es um die Anordnung von Kindesschutzmassnahmen (Unterbringung eines Kindes in einem Heim) und damit um eine öffentlich-rechtliche Angelegenheit in unmittelbarem Zusammenhang mit Zivilrecht (Art. 72 Abs. 2 lit. b Ziff. 6 BGG) ohne Vermögenswert. Die Beschwerde in Zivilsachen ist damit grundsätzlich gegeben. Die Beschwerdeführer sind gemäss <ref-law> zur Beschwerde berechtigt und die Beschwerdefrist ist eingehalten (<ref-law>). Insofern kann auf die Beschwerde eingetreten werden.
1.2. Da es sich um vorsorgliche Massnahmen handelt, kann nur die Verletzung verfassungsmässiger Rechte gerügt werden (<ref-law>). Hierfür gilt das strenge Rügeprinzip (<ref-law>). Das bedeutet, dass das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen prüft, während es auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid nicht eintritt (<ref-ruling> E. 2.2 S. 246).
1.3. Gegenstand des bundesgerichtlichen Verfahrens bildet nur die angemessene Unterbringung des Kindes gemäss <ref-law>, jedoch nicht der Obhutsentzug an sich. Die Vorinstanz hat festgestellt, dass den Beschwerdeführern die Obhut bereits mit Verfügungen der KESB vom 5./10. Dezember 2012 entzogen wurde. Diese hätten den Obhutsentzug damals nicht angefochten, weshalb diese Anordnung in Rechtskraft erwachsen sei. Bereits im vorinstanzlichen Verfahren wurde einzig die Unterbringung beurteilt, was die Beschwerdeführer im Übrigen auch nicht beanstanden.
Der Kammerentscheid der KESB vom 17. Mai 2013 bildet ebenfalls nicht Gegenstand dieses Verfahrens. Dasselbe gilt für die diversen weiteren Eingaben des Beschwerdeführers, welche nicht den angefochtenen Entscheid betreffen.
1.4. Die vorliegend umstrittene Unterbringung der Tochter der Beschwerdeführer wurde am 31. Januar (superprovisorisch) resp. am 19. Februar 2013 von der KESB Z._ angeordnet und am 19. April 2013 von der Vorinstanz bestätigt. Daher kommen die am 1. Januar 2013 in Kraft getretenen neuen Bestimmungen des Kindesschutzrechts zur Anwendung (<ref-law>; vgl. Bundesgesetz vom 19. Dezember 2008 zum Erwachsenenschutz, Personenrecht und Kindesrecht, AS 2011 725).
2.
Die Beschwerdeführer bezeichnen ihre Eingabe als "Rechtsverweigerungsbeschwerde" und beanstanden, dass die Vorinstanz einen schriftlichen Entscheid gefällt habe, obwohl sie hätten davon ausgehen können, einer mündlichen Verhandlung beiwohnen zu dürfen. Durch den schriftlichen Entscheid habe die Vorinstanz willkürlich eine öffentliche Verhandlung umgangen. Daran angeknüpft beantragen sie eine "ordentliche Gerichtsverhandlung".
2.1. Art. 6 Ziff. 1 EMRK garantiert die Öffentlichkeit des Verfahrens. Dieser Grundsatz umfasst unter anderem das Recht des Einzelnen, seine Argumente dem Gericht mündlich in einer öffentlichen Sitzung vorzutragen. Die Pflicht zur Durchführung einer öffentlichen Verhandlung setzt indes einen klaren Parteiantrag voraus. Blosse Beweisabnahmeanträge, wie der Antrag auf Durchführung einer persönlichen Befragung, reichen nicht aus (<ref-ruling> E. 5.2 S. 147).
In beiden kantonalen Beschwerden beantragten die Beschwerdeführer eine persönliche Anhörung durch die Beschwerdeinstanz. Diese teilte den Parteien mit Verfügung vom 12. März 2013 mit, dass das Verfahren schriftlich, d.h. ohne Parteiverhandlung erledigt werde. Daraufhin liessen sich die Beschwerdeführer durch ihre Anwältin mit Eingabe vom 14. März 2013 an die Vorinstanz wie folgt vernehmen:
"In Bezug auf Ihre Verfügung vom 12. März 2013 teile ich Ihnen mit, dass die Beschwerdeführer nicht einverstanden sind, dass über das Verfahren schriftlich entschieden wird. Es wird eine mündliche Parteiverhandlung verlangt. Als Beweismittel wurde ausdrücklich die Parteibefragung verlangt. Diese ist für den vorliegenden Entscheid zentral, da sich das angerufene Gericht unbedingt selber ein Bild von den Beschwerdeführern machen muss. Verzichtet das angerufene Gericht auf eine mündliche Parteiverhandlung, verletzt sie nicht nur das Recht der Beschwerdeführer auf Beweisabnahme, sondern vor allem auch das rechtliche Gehör der Beschwerdeführer."
Die Vorinstanz ging auf das Schreiben nicht gesondert ein. Erst im Entscheid vom 19. April 2013 findet sich der Hinweis, den Parteien sei am 12. März 2013 mitgeteilt worden, dass das Verfahren schriftlich erledigt werde. Inhaltlich setzte sie sich mit den Anträgen auf persönliche Anhörung nicht auseinander.
Nach dem Dargelegten haben die Beschwerdeführer keinen Antrag auf Durchführung einer öffentlichen Verhandlung gestellt, sondern um eine mündliche Anhörung im Sinne eines Beweisantrages ersucht. Art. 6 Ziff. 1 EMRK hat im vorliegenden Fall daher keine über <ref-law> hinausgehende Bedeutung.
2.2. Der verfassungsmässige Anspruch auf rechtliches Gehör (<ref-law>) gewährleistet dem Betroffenen das Recht, von den Akten Kenntnis zu nehmen (<ref-ruling> E. 2b S. 10), sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheides zu äussern, erhebliche Beweise vorzulegen, und das Recht, mit seinen Beweisofferten zu erheblichen Tatsachen zugelassen zu werden, der Beweisabnahme beizuwohnen oder mindestens sich zum Beweisergebnis zu äussern (<ref-ruling> E. 2c S. 578; <ref-ruling> E. 2.2 S. 504; <ref-ruling> E. 3.2 S. 494). <ref-law> räumt per se aber keinen Anspruch auf mündliche Anhörung ein (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2.1 S. 428).
Der hier zur Debatte stehende Teilgehalt des Beweisführungsrechts steht einer vorweggenommenen Beweiswürdigung nicht entgegen. Das Gericht kann auf die Abnahme von Beweisen verzichten, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148 mit weiteren Hinweisen). Auch die Tatsache, dass ein Verfahren - wie vorliegend - der Untersuchungsmaxime unterliegt, steht einer antizipierten Beweiswürdigung nicht entgegen (<ref-ruling> E. 2.2.3 S. 735; Urteil 5A_361/2010 vom 10. September 2010 E. 4.2.1, in: FamPra.ch 2011 S. 218). Nur wenn die Beweiswürdigung offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, auf einem offenkundigen Versehen beruht oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft, ist durch die Nichtabnahme eines Beweismittels das rechtliche Gehör verletzt (BGE <ref-ruling> E. 2.1 S. 428 f.; <ref-ruling> E. 4a S. 211). Diese Rechtsprechung hat für den Beschwerdeführer zur Folge, dass er - wenn das Sachgericht eine rechtserhebliche Tatsache als bewiesen oder als widerlegt erachtet - in einem ersten Schritt - und unter Gewärtigung der Nichteintretensfolge - willkürliche Beweiswürdigung rügen und damit durchdringen muss, bevor sich das Bundesgericht mit der Rüge der Verletzung des Beweisführungsanspruchs nach <ref-law> befasst.
Nun erheben die Beschwerdeführer weder eine Sachverhaltsrüge noch führen sie aus, was sie zur Frage der Unterbringung der Tochter hätten ausführen wollen respektive können, das die Vorinstanz zu einem anderen Entscheid hätte bewegen sollen. Daher ist dem Vorwurf der Verletzung des rechtlichen Gehörs die Grundlage entzogen (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157) und auf die Rüge ist nicht einzutreten.
2.3. Weitere Verfassungsrügen erheben die Beschwerdeführer nicht in Bezug auf die beantragte Anhörung (vgl. vorstehend E. 1.2).
Ob allenfalls das kantonale Verfahrensrecht weitergehende Parteirechte vorsieht (vgl. <ref-law>; Gesetz des Kantons Bern über den Kindes- und Erwachsenenschutz [ KESG ] ), kann offen bleiben, da die Beschwerdeführer keine Verletzung des kantonalen Rechts gerügt haben (<ref-law> ).
3.
In der Sache selbst erschöpfen sich die Beschwerde wie auch das Schreiben vom 27. April 2013 in einer stichwortartigen Auflistung des Sachverhalts aus der Sicht der Beschwerdeführer und in Vorwürfen an die Vorinstanzen. Ein Begehren in der Sache lässt sich den Eingaben nicht entnehmen. Zwar halten die Beschwerdeführer sinngemäss fest, dass sie eine Mutter-Kind-Platzierung ablehnen, sie äussern sich aber weder zur Unterbringung des Kindes als solche, noch thematisieren sie die Eignung der von der KESB gewählten Einrichtung.
Damit ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
4.
Bei diesem Verfahrensausgang werden die Beschwerdeführer kostenpflichtig (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern auferlegt.
3.
Dieses Urteil wird den Parteien, der Kindes- und Erwachsenenschutzbehörde KESB Z._ und dem Obergericht des Kantons Bern, Zivilabteilung, Kindes- und Erwachsenenschutzgericht, schriftlich mitgeteilt.
Lausanne, 15. Juli 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Die Gerichtsschreiberin: Friedli-Bruggmann