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.

Erwägungen:
1. 1.1 Beim angefochtenen Entscheid handelt es sich um eine letztinstanzliche (<ref-law>) Beurteilung der fürsorgerischen Freiheitsentziehung, mithin um eine Zivilsache im Sinn von Art. 72 Abs. 2 lit. b Ziff. 6 BGG, die grundsätzlich mit Beschwerde in Zivilsachen angefochten werden kann. Da im vorliegenden Fall aber nur die Parteientschädigung streitig ist und der Streitwert Fr. 30'000.-- bei weitem nicht erreicht wird, ist nur die subsidiäre Verfassungsbeschwerde gegeben (<ref-law>; <ref-law>; vgl. Urteil 5D_88/2008 vom 14. August 2008 E. 1). Auf die Beschwerde in Zivilsachen ist nicht einzutreten.
1.2 Beide Beschwerdeführer verfügen über ein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids (<ref-law>; vgl. 5P.241/2000 vom 10. Januar 2001).
2. 2.1 Der angefochtene Entscheid hat die Entschädigung des Beschwerdeführers ohne Begründung festgesetzt. Nach der mündlich nachgelieferten "Erläuterung" des Präsidenten der Rekurskommission wird der geltenden Praxis folgend, in Fällen, in denen wie hier Kostenerlass für den Fall des Unterliegens beantragt wird, auch bei Obsiegen der Partei nur ein reduziertes Anwaltshonorar (Fr. 180.-- pro Stunde) ausgerichtet; ein volles Honorar (Fr. 220.-- pro Stunde) wird nur dann gesprochen, wenn kein Kostenerlass verlangt wird. Die Rekurskommission hat daher ein Honorar von Fr. 1'555.90 zuerkannt, das sich aus einer Entschädigung von 8 Stunden zu Fr. 180.--/Std., aus den Telefonkosten von Fr. 6.-- gemäss Honorarnote und der Mehrwertsteuer von 7.6% zusammensetzt.
2.2 Der Beschwerdeführer macht geltend, aus der von der Rekurskommission geübten Praxis ergebe sich für den konkreten Fall, dass ihm eine ordentliche Parteientschädigung von Fr. 1'900.20 (8 Std. zu Fr. 220.--/Std. zuzüglich Fr. 6.-- Telefonkosten und Mehrwertsteuer von 7.6%) zugesprochen worden wäre, wenn die Beschwerdeführerin im Verfahren keinen Eventualantrag auf unentgeltliche Prozessführung gestellt hätte. Die Vorinstanz übersehe mit ihrer Praxis, dass es mit der Bestellung eines unentgeltlichen Rechtsbeistandes nicht darum gehe, die unterliegende Partei von der Bezahlung einer Parteientschädigung zu entlasten, sondern der bedürftigen Partei den Zugang zum Gericht zu ermöglichen. Nach der Rechtsprechung des Bundesgerichts (Urteil 5P.421/2000 vom 10 Januar 2001) habe der öffentlich-rechtliche Entschädigungsanspruch subsidiären Charakter und bleibe daher ohne Einfluss auf die Prozessentschädigung des unterliegenden Prozessgegners. Er komme nur zum Tragen, wenn keine Prozessentschädigung geschuldet oder diese uneinbringlich sei, weshalb kein sachlicher Grund bestehe, die Entschädigung der obsiegenden Partei nur deshalb zu kürzen, weil ihr ein unentgeltlicher Rechtsbeistand bestellt worden sei. Die von der Vorinstanz vorgenommene Unterscheidung verletze Art. 8 Abs. 1 und <ref-law>. Aufgrund dieser Überlegungen sei der angefochtene Kostenentscheid aufzuheben und die Entschädigung auf Fr. 1'900.20 festzusetzen.
2.3 Entgegen der Auffassung der Rekurskommission erweist sich die Beschwerde mit den vorgenannten Ausführungen als genügend begründet, werden doch darin die als verletzt erachteten Bestimmungen erwähnt; ferner wird verständlich aufgezeigt, inwiefern diese Bestimmungen durch den angefochtenen Entscheid verletzt worden sein sollen. Dass nicht auf kantonale Normen Bezug genommen worden ist, schadet den Beschwerdeführern nicht (siehe dazu E. 3.2). Unter dem Gesichtspunkt der Begründungsanforderungen (<ref-law>; <ref-ruling> E. 6 S. 397) kann auf die Beschwerde eingetreten werden.
2.4 Im Übrigen macht die Rekurskommision geltend, der Möglichkeit, im Fall des Obsiegens eine Parteientschädigung zuzusprechen, stehe die Verpflichtung der Behörde gegenüber, den Rekurrierenden die unentgeltliche Rechtspflege zu gewähren, wenn deren Voraussetzungen erfüllt seien. Es bestehe keine durch ein kantonales Gesetz begründete Verpflichtung, dem obsiegenden Rekurrenten für die ihm entstandenen Anwaltskosten eine Parteientschädigung auszurichten. Weder aus dem Psychiatriegesetz noch aus anderen das Rekursverfahren regelnden Gesetzen des Kantons Basel-Stadt ergebe sich, dass der Entschädigung des unentgeltlichen Rechtsbeistands im Verhältnis zur Ausrichtung einer Parteientschädigung subsidiären Charakter zukomme. Durch die Entschädigung des Rechtsbeistands unabhängig vom Ausgang des Verfahrens nach den Grundsätzen der unentgeltlichen Rechtspflege entstehe der verbeiständeten Person kein Nachteil, zumal das Psychiatriegesetz auch im Fall der verbesserten wirtschaftlichen Verhältnisse des Verbeiständeten keine Rückerstattung von im Rahmen der unentgeltlichen Rechtspflege bezahlten Anwaltskosten vorsehe. Sodann habe der amtliche Rechtsbeistand eine Kürzung des Honorars hinzunehmen und er sei nicht berechtigt, von der verbeiständeten Person ein zusätzliches Honorar zu verlangen. Mit der Bewilligung der unentgeltlichen Verbeiständung trete der Rechtsbeistand des Rekurrenten in ein besonderes Auftragsverhältnis zum Gemeinwesen; seine Entschädigung richte sich unter diesen Umständen nach dem einschlägigen kantonalen Recht. Der im Rahmen der unentgeltlichen Rechtspflege verbeiständete Anwalt müsse gegenüber einer Entschädigung im Falle "normalen Obsiegens" einen etwas niedrigeren Stundenansatz akzeptieren, trage aber gleichzeitig nicht das Risiko, sein Honorar im Fall der Abweisung des Rekurses nicht oder nicht vollständig erhältlich machen zu können.
3. 3.1 Nach § 25 Abs. 3 des auf die fürsorgerische Freiheitsentziehung anwendbaren Gesetzes über Behandlung und Einweisung psychisch kranker Personen (Psychiatriegesetz) vom 18. September 1996 sind im Rekursverfahren die Grundsätze der unentgeltlichen Verbeiständung anwendbar. Gemäss § 41 Abs. 1 des Gesetzes ist das Verfahren vor der Rekurskommission kostenlos, wenn auch bei offensichtlich mutwilliger Rekurs- oder Beschwerdeführung eine Spruchgebühr auferlegt werden kann. Einer ganz oder teilweise obsiegenden Partei, der Anwaltskosten entstanden sind, kann eine angemessene Parteientschädigung zugesprochen werden (§ 41 Abs. 2 ).
3.2 Ob sich aus dem Psychiatriegesetz oder aus anderen das Rekursverfahren regelnden Gesetzen des Kantons Basel-Stadt die Subsidiarität der Entschädigung des amtlichen Rechtsbeistands gegenüber der ordentlichen von der unterliegenden Partei zu entrichtenden Parteientschädigung herleiten lässt, ist hier nicht von Bedeutung. Einem allgemeinen prozessualen Leitsatz entspricht, dass grundsätzlich jede Partei die andere nach Massgabe ihres Unterliegens zu entschädigen hat. Der Umstand, dass der obsiegenden Partei ein unentgeltlicher Rechtsbeistand bewilligt worden ist, befreit die unterliegende nicht von der Leistung einer Prozessentschädigung (<ref-ruling> E. 3 S. 296; Frank/Sträuli/Messmer, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. Zürich 2000, N. 1 zu <ref-law>). Der öffentlich-rechtliche Entschädigungsanspruch des amtlichen Anwalts hat subsidiären Charakter und bleibt ohne Einfluss auf die Prozessentschädigung des unterliegenden Gegners. Er kommt zum Tragen, wenn keine Prozessentschädigung geschuldet oder diese uneinbringlich ist. Dass die obsiegende Partei von einem unentgeltlichen Rechtsbeistand vertreten wird, ist somit keine wesentliche Tatsache für die Festsetzung der Parteienschädigung (Urteil 5P.421/2000 vom 10. Januar 2001 E. 3b). An der Anwendbarkeit des aufgezeigten Grundsatzes ändert nichts, dass im vorliegenden Fall die Parteientschädigung nicht von einem privaten Prozessgegner, sondern von der öffentlichen Hand geschuldet ist (vgl. <ref-ruling> E. 3d S. 327). Auch das bundesgerichtliche Verfahren geht von der Subsidiarität der amtlichen Entschädigung aus, wird doch dem amtlichen Rechtsbeistand der obsiegenden im Genuss der unentgeltlichen Rechtspflege prozessierenden Partei erst dann eine reduzierte Entschädigung aus der Bundesgerichtskasse entrichtet, wenn die der obsiegenden Partei zulasten des unterliegenden Prozessgegners zugesprochene Parteientschädigung nicht erhältlich gemacht werden kann (<ref-law>). Wird das unterliegende Gemeinwesen zu einer ordentlichen Entschädigung an den obsiegenden, im Genuss der unentgeltlichen Rechtspflege prozessierenden Gegner verurteilt (<ref-law>), wird das Gesuch um unentgeltliche Rechtspflege des obsiegenden Gegners in aller Regel gegenstandslos (<ref-ruling> E. 3 S. 248). Zusammenfassend besteht somit kein Grund, die Entschädigung der obsiegenden Partei nur deshalb zu kürzen, weil ihr ein unentgeltlicher Rechtsbeistand bestellt worden ist. Der Entscheid der Rekurskommission verletzt daher den Rechtsgleichheitsgrundsatz (<ref-law>) sowie das Willkürverbot (<ref-law>). Die subsidiäre Verfassungsbeschwerde erweist sich damit als begründet.
4. 4.1 Heisst das Bundesgericht die Beschwerde gut, entscheidet es in der Sache selbst oder weist sie zu neuer Beurteilung an die Vorinstanz zurück (<ref-law>). Diese Bestimmung ist aufgrund des Verweises in <ref-law> auch auf die Verfassungsbeschwerde anwendbar. Somit ist auch bei einer Gutheissung der Verfassungsbeschwerde nicht einfach nur der angefochtene Entscheid aufzuheben, sondern in der Sache selbst zu entscheiden, sofern die erforderlichen Sachverhaltsfeststellungen getroffen worden sind (Urteil 4D_48/2007 vom 13. November 2007 E. 1.1; vgl. <ref-ruling> E. 3.1 mit Hinweisen).
4.2 Paragraph 41 Abs. 2 Psychiatriegesetz verweist bezüglich der Entschädigung der obsiegenden Partei für entstandene Anwaltskosten auf das richterliche Ermessen ("kann"). Im vorliegenden Fall hat die Rekurskommission den Beschwerdeführer als amtlichen Rechtsbeistand bestellt und hat demzufolge die anwaltliche Verbeiständung der Beschwerdeführerin im Rekursverfahren als erforderlich betrachtet. Weder aus dem angefochtenen Entscheid noch aus der Vernehmlassung der Vorinstanz ergeben sich Anhaltspunkte, die eine Entschädigung der Beschwerdeführerin für entstandene Anwaltskosten ausschliessen würden. Es kann entgegen der Auffassung der Rekurskommission nicht gesagt werden, die Kommission wäre bei pflichtgemässer Ausübung des Ermessens nicht verpflichtet gewesen, die anwaltlich vertretene, in der Sache obsiegende Beschwerdeführerin für die entstandenen Anwaltskosten zu entschädigen. Des weiteren sind auch die einzelnen Positionen der Kostenliste des Beschwerdeführers sowie der Stundenansatz von Fr. 220.-- nicht bestritten. Dem Antrag auf Ausrichtung einer Entschädigung von Fr. 1'900.20 (inkl. 7.6 MWST) ist somit zu entsprechen.
5. Die Beschwerdeführer obsiegen zur Hauptsache. Im vorliegenden Fall sind Vermögensinteressen des unterliegenden Kantons Basel-Stadt betroffen, weshalb er zur Bezahlung von Gerichtskosten verhalten werden kann (<ref-law> e contrario). Des weiteren hat der Kanton die Beschwerdeführer für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>).
6. Mit der vorliegenden Kosten- und Entschädigungsregelung wird das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren gegenstandslos.

Demnach erkennt das Bundesgericht:
1. 1.1 Auf die Beschwerde in Zivilsachen wird nicht eingetreten. Die subsidiäre Verfassungsbeschwerde wird gutgeheissen und Ziff. 3 des Entscheids der Psychiatrie-Rekurskommission vom 16. April 2009 aufgehoben.
1.2 Der Kanton Basel-Stadt hat die Beschwerdeführerin für das Rekursverfahren mit Fr. 1'900.20 (inkl. MWST) zu entschädigen.
2. Das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird als gegenstandslos abgeschrieben.
3. Die Gerichtskosten von Fr. 200.-- werden dem Kanton Basel-Stadt auferlegt.
4. Der Kanton Basel-Stadt hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt mit Fr. 600.-- zu entschädigen.
5. Dieses Urteil wird den Beschwerdeführern und der Psychiatrie-Rekurskommission Basel-Stadt schriftlich mitgeteilt.
Lausanne, 29. Juni 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zbinden