Sachverhalt: A. A._ (geb. 1976; norwegischer Staatsangehöriger) und B._ (geb. 1979; US-amerikanische Staatsangehörige) sind die nicht miteinander verheirateten Eltern der Tochter C._ (geb. 2007). Die Eltern zogen im Juli 2009 von T._ (Niederlande) nach U._ (GE). Im Herbst 2009 trat die Mutter eine Stelle in V._ (Vereinigtes Königreich) an. Sie kehrte ein Jahr später in die Schweiz zurück und mietete in W._ (GE) eine Wohnung. C._ lebte von Oktober 2009 bis zu den Sommerferien 2011 bei ihrem Vater in U._ und danach bei ihrer Mutter in W._. Im Jahr 2012 vermählten sich beide Eltern mit je einem neuen Partner; aus der neuen Verbindung der Mutter ging C._s Halbbruder F._ (geb. 2012) hervor. B. Mit Entscheid vom 22. Dezember 2011 ordnete die Kindes- und Erwachsenenschutzbehörde X._ für C._ eine Beistandschaft nach Art. 308 Abs. 1 und 2 ZGB an. Ausserdem verfügte sie eine Weisung nach Art. 307 Abs. 3 ZGB. Die Cour de Justice des Kantons Genf bestätigte diesen Entscheid am 30. Mai 2012. In der Folge versuchte A._ vergeblich zu erwirken, dass der Mutter die Obhut über C._ entzogen und das Kind bei ihm platziert wird. Das Bundesgericht bestätigte den Entscheid der Kindes- und Erwachsenenschutzbehörde X._ vom 21. Dezember 2012, wonach die Voraussetzungen für einen Entzug der Obhut nicht erfüllt seien (vgl. Urteil 5A_869/2013 vom 24. März 2014). C. Nachdem B._ nach Y._ (LU) umgezogen war, übernahm mit Entscheid vom 20. Mai 2014 die Kindes- und Erwachsenenschutzbehörde Z._ (im Folgenden KESB Z._) die für C._ geführten Kindesschutzmassnahmen. Die KESB Z._ setzte einen neuen Beistand ein, hob die Beistandschaft nach Art. 308 Abs. 1 ZGB sowie die Weisung nach Art. 307 Abs. 3 ZGB ersatzlos auf und definierte gestützt auf Art. 308 Abs. 2 ZGB die Aufgaben des Beistandes neu. D. D.a. Am 18. Juli 2014 beantragte A._ die gemeinsame elterliche Sorge für C._, evtl. das alleinige Sorgerecht. Am 5. November 2014 ersuchte der Beistand um Erteilung der Prozessvollmacht für die klageweise Geltendmachung von Kinderunterhaltsbeiträgen für C._. Darauf reagierte A._ mit dem Antrag, einen anderen Beistand einzusetzen. D.b. Mit Entscheid vom 30. Juni 2015 wies die KESB Z._ die Anträge von A._ ab. D.c. Gegen diesen Entscheid erhob A._ Verwaltungsgerichtsbeschwerde beim Kantonsgericht Luzern. Dieses wies das Rechtsmittel mit Urteil vom 23. November 2015 ab, sowohl was das Begehren betreffend die gemeinsame elterliche Sorge angeht als auch mit Bezug auf das Eventualbegehren um Zuteilung des alleinigen Sorgerechts. E. E.a. Mit Beschwerde in Zivilsachen vom 13. Januar 2016 wendet sich A._ (Beschwerdeführer) an das Bundesgericht. Er beantragt, die elterliche Sorge über die gemeinsame Tochter C._ den Parteien gemeinsam zu erteilen. Eventualiter sei die Sache zur Neubeurteilung an das Kantonsgericht zurückzuweisen, damit dieses die gemeinsame elterliche Sorge für C._ den Parteien gemeinsam erteilt. Zudem verlangt der Beschwerdeführer, die Verfahrenskosten der KESB Z._ und des vorinstanzlichen Beschwerdeverfahrens B._ (Beschwerdegegnerin) aufzuerlegen. E.b. Eingeladen, sich zur Beschwerde vernehmen zu lassen, beantragt die Beschwerdegegnerin, alle Anträge des Beschwerdeführers abzuweisen (Eingabe vom 20. Mai 2016). Das Kantonsgericht Luzern liess sich nicht vernehmen. Am 6. Juni 2016 liess der Beschwerdeführer eine Replik einreichen, in der er an seinen Beschwerdebegehren festhält. Im Übrigen hat sich das Bundesgericht die vorinstanzlichen Akten überweisen lassen.