Sachverhalt: A. X._ trat am 1. April 2009 freiwillig in die Psychiatrische Klinik A._ ein. Im Verlaufe des Eintrittstages wünschte sie, die Klinik wieder zu verlassen, weshalb ihr die Ärztin des Gesundheitsdienstes fürsorgerisch die Freiheit entzog. B. X._ gelangte dagegen mit Rekurs vom 6. April 2009 an die Psychiatrie-Rekurskommission des Kantons Basel-Stadt und ersuchte um Entlassung. Ferner stellte sie das Begehren, die Kosten des Verfahrens dem Gemeinwesen aufzuerlegen, subsidiär ihr im Fall des Unterliegens den Kostenerlass (die unentgeltliche Rechtspflege) zu gewähren. Mit Entscheid vom 16. April 2009 hiess die Kommission den Rekurs gut, bewilligte der Rekurrentin die unentgeltliche Rechtspflege und sprach dem Rechtsvertreter, Y._, ein (reduziertes) Honorar von Fr. 1'555.90 (inkl. 7.6% MWST) zulasten des Gesundheitsdepartementes Basel-Stadt zu. C. X._ und ihr amtlicher Rechtsbeistand, Y._, haben gegen diesen Entscheid am 11. Mai 2009 Beschwerde in Zivilsachen und subsidiäre Verfassungsbeschwerde erhoben. Sie beantragen, den Kostenentscheid der Vorinstanz aufzuheben und der Beschwerdeführerin für das Verfahren vor der Psychiatrie-Rekurskommission eine Parteientschädigung von Fr. 1'900.20 (inkl. MWST) zuzusprechen. Die Kosten des Verfahrens vor Bundesgericht seien der Psychiatrie-Rekurskommission aufzuerlegen. Eventualiter sei der Beschwerdeführerin der Kostenerlass für die Kosten des bundesgerichtlichen Verfahrens zu bewilligen. Die Psychiatrie-Rekurskommission schliesst auf Abweisung der Beschwerden. 