Sachverhalt: A. A.A._ und B.A._ hatten am 29. Januar 1993 geheiratet. Aus der Ehe gingen vier Kinder hervor: Die Zwillinge C.A._ und D.A._ (geb. 1993), E.A._ (geb. 1995) und F.A._ (geb. 1997). Mit Entscheid vom 29. Oktober 2012 schied das Bezirksgericht Surselva die Ehe der Eltern. Die Kinder E.A._ und F.A._ wurden unter die elterliche Sorge der Mutter gestellt. Der Vater wurde verpflichtet, E.A._ und F.A._ Alimente in der Höhe von je Fr. 800.-- pro Monat zu zahlen. B. B.a. Am 17. Oktober 2014 reichte A.A._ beim Kantonsgericht Appenzell Ausserrhoden gegen B.A._ und seinen Sohn E.A._ eine 8-seitige Klage auf Abänderung des Scheidungsurteils ein. Unter Ziffer 4 seiner Rechtsbegehren stellte er den Verfahrensantrag, die Parteien zu einer Einigungsverhandlung vorzuladen. B.b. In der Folge machte die Einzelrichterin des Kantonsgerichts den Rechtsvertreter von A.A._ darauf aufmerksam, dass er gegen den Sohn E.A._ im vereinfachten Verfahren mit vorhergehender Schlichtung klagen müsse. Darauf zog A.A._ die Klage gegen E.A._ am 3. November 2014 zurück. B.c. Mit Verfügung vom 26. November 2014 stellte die Einzelrichterin die Klage B.A._ zu und forderte sie auf, binnen dreissig Tagen eine Klageantwort einzureichen. Mit dieser Aufforderung war der Hinweis verbunden, dass zu den Anträgen des Klägers eigene Anträge zu stellen und zu begründen seien; soweit es sich um finanzielle Begehren handele, seien die Anträge zu beziffern. Zu den behaupteten Tatsachen seien die einzelnen Beweismittel zu bezeichnen. Die verfügbaren Urkunden, die als Beweismittel dienen sollen, seien beizulegen (versehen mit einem nummerierten Verzeichnis). Eine Kopie dieser Verfügung ging an A.A._. B.d. Mit Entscheid vom 19. Dezember 2014 wies die Einzelrichterin des Kantonsgerichts A.A._s Gesuch um unentgeltliche Rechtspflege mangels Bedürftigkeit ab. Nachdem der Entscheid in Rechtskraft erwachsen war, forderte sie A.A._ mit Verfügung vom 9. Januar 2015 auf, einen Kostenvorschuss von Fr. 800.-- zu bezahlen. Gleichentags ersuchte B.A._ um Erstreckung der Frist für die Einreichung der Klageantwort. Die Einzelrichterin entsprach dem Gesuch am 12. Januar 2015; eine Kopie dieses Entscheids ging an A.A._. B.e. Am 2. Februar 2015 ging die 12-seitige Klageantwort von B.A._ beim Kantonsgericht Appenzell Ausserrhoden ein. Die Eingabe wurde unverzüglich dem Rechtsvertreter von A.A._ zugestellt. B.f. Mit Schreiben vom 3. März 2015 zog A.A._ auch seine Klage gegen B.A._ zurück. B.g. Am 10. März 2015 reichte die Rechtsvertreterin von B.A._ beim Kantonsgericht ihre Kostennote ein. B.h. Mit Entscheid vom 12. März 2015 schrieb die Einzelrichterin des Kantonsgerichts Appenzell Ausserrhoden das Verfahren zufolge Rückzugs der Klage als erledigt ab. Sie auferlegte A.A._ die Verfahrenskosten von Fr. 300.-- und verurteilte ihn, B.A._ eine Parteientschädigung von Fr. 2'522.05 (inkl. Barauslagen und MWSt) zu bezahlen. C. A.A._ erhob gegen den Kostenentscheid Beschwerde beim Obergericht des Kantons Appenzell Ausserrhoden. Dieses wies das Rechtsmittel ab, auferlegte A.A._ die Kosten des Beschwerdeverfahrens von Fr. 800.-- und verpflichtete ihn, B.A._ eine Prozessentschädigung von Fr. 1'296.-- zu bezahlen (Entscheid vom 28. Oktober 2015). D. Mit Beschwerde und subsidiärer Verfassungsbeschwerde vom 30. November 2015 wendet sich A.A._ (Beschwerdeführer) an das Bundesgericht. Er verlangt, das Urteil des Obergerichts aufzuheben. Eventualiter sei seine Entschädigungspflicht im erstinstanzlichen Verfahren (Bst. B.h) auf einen Betrag von maximal Fr. 498.95 festzulegen und entsprechend auch im Beschwerdeverfahren angemessen zu reduzieren. Ferner verlangt der Beschwerdeführer für das Verfahren vor dem Bundesgericht die unentgeltliche Rechtspflege und Verbeiständung. Eingeladen, sich zur Beschwerde vernehmen zu lassen, beantragt B.A._, das Rechtsmittel abzuweisen, soweit überhaupt darauf eingetreten werden kann (Eingabe vom 25. April 2016). Das Obergericht und das Kantonsgericht haben auf eine Vernehmlassung verzichtet und im Übrigen auf die Begründung im angefochtenen Entscheid verwiesen (Schreiben vom 5. bzw. 6. April 2016). Zur Wahrung des rechtlichen Gehörs wurden diese Eingaben dem Beschwerdeführer zur Kenntnis gebracht.