Sachverhalt: A. A.a. Die zuständige niederländische Steuerbehörde (Belastingdienst [BD]) richtete am 7. Mai 2018 gestützt auf Art. 26 des Abkommens zwischen der Schweizerischen Eidgenossenschaft und dem Königreich der Niederlande zur Vermeidung der Doppelbesteuerung auf dem Gebiet der Steuern vom Einkommen (DBA CH-NL; SR 0.672.963.61) ein Amtshilfegesuch an die Eidgenössische Steuerverwaltung (ESTV), welches die in den Niederlanden steuerpflichtige A._ betrifft. Das Amtshilfegesuch bezieht sich auf die Einkommenssteuern der letzteren für den Zeitraum 1. Januar 2011 bis 31. Dezember 2017. Der BD nimmt im Amtshilfegesuch Bezug auf ein bestimmtes Bankkonto bei der Bank C._, U._, lautend auf A._. Aus den vorhandenen Unterlagen gehe hervor, dass das Konto im Mai 2011 eröffnet worden sei. Am 23. Mai 2011 sei ein Betrag von Fr. 1'258'100.-- mit einem Checkvermerk auf das Konto einbezahlt worden, wobei A._ diesbezüglich ausgeführt habe, es handle sich um eine Bareinzahlung. Gemäss dem letzten Kontoauszug werde "statement of account closing zum 21.08.2015" und scheinbar lediglich der Betrag von Fr. 1'255'544.93 angegeben. Auf entsprechende Nachfrage der Steuerverwaltung habe A._ dazu gesagt, der Betrag sei in bar abgehoben worden. In diesem Zusammenhang ersucht der BD um detaillierte Angaben zur Herkunft der genannten Einzahlung (insbesondere Name der Bank und des Kontoinhabers, falls der Betrag von einem anderen Bankkonto überwiesen wurde) und zum Verbleib des genannten, vermeintlichen Endbetrages (von Fr. 1'255'544.93). In Bezug auf letzteres ersucht der BD, falls der Endbetrag auf ein anderes Konto transferiert wurde, insbesondere um Angabe der entsprechenden Kontonummer und der Namen der Bank und des Kontoinhabers. A.b. Im genannten Amtshilfegesuch hielt der BD fest: "Ich bestätige, dass alle üblichen Ermittlungsmöglichkeiten ausgeschöpft sind." Nachdem A._ mit Eingabe vom 11. September 2018 die Einhaltung des Subsidiaritätsprinzips bestritten hatte, wandte sich die ESTV mit E-Mail vom 17. Oktober 2018 an den BD und führte aus, gemäss der genannten Beanstandung sei in den Niederlanden die sogenannte Informationsverfügung noch nicht erlassen worden, weshalb um die Beantwortung folgender Fragen gebeten werde: "Dürfen wir davon ausgehen, dass im niederländischen innerstaatlichen Verfahren betreffend A._ auch ohne Eröffnung einer solchen Informationsverfügung alle (üblichen) Mittel im Sinne von Ziffer XVI Buchstabe a des integrierenden Bestandteil des DBA CH-NL bildenden Protokolls ausgeschöpft sind, um die für die Steuererhebung benötigten Informationen zu erlangen, wie dies bereits im Ersuchen vom 7. Mai 2018 bestätigt wurde? Ferner wären wir Ihnen dankbar für eine kurze Erläuterung der Grundzüge des niederländischen Instituts der Informationsverfügung." Die Vertreterin des BD erwiderte mit E-Mail vom 22. Oktober 2018: "In Antwort auf Ihre Frage bestätige ich, dass auch ohne Eröffnung einer Informationsverfügung alle (üblichen) Mittel ausgeschöpft sind." Im Weiteren erläuterte sie das Institut der "Auskunftsverfügung". B. Mit Schlussverfügung vom 14. Januar 2019 ordnete die ESTV die Übermittlung der ersuchten Informationen an den BD an, unter anderem auch die Information, wonach der vorgenannte Endbetrag am 21. August 2015 auf ein Konto bei der Bank D._, lautend auf "B._", überwiesen worden war. Die dagegen von A._ und B._ erhobene Beschwerde vom 12. Februar 2019 wurde vom Bundesverwaltungsgericht mit Urteil vom 20. September 2019 abgewiesen. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 10. Oktober 2019 beantragen A._ (Beschwerdeführerin) und B._ (Beschwerdeführer) die Aufhebung des vorinstanzlichen Urteils und der genannten Schlussverfügung der ESTV. Dem BD sei bezüglich der Beschwerdeführer keine Amtshilfe zu leisten. Eventualiter seien das vorinstanzliche Urteil und die genannte Schlussverfügung der ESTV aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem sei der Beschwerde die aufschiebende Wirkung zu erteilen. Während die Vorinstanz in ihrer Vernehmlassung auf das angefochtene Urteil verweist, beantragt die ESTV mit Eingabe vom 6. November 2019, auf die Beschwerde nicht einzutreten, eventualiter diese abzuweisen. Die Beschwerdeführer haben mit Eingabe vom 18. November 2019 repliziert.