Sachverhalt:
A. X._ wird dringend verdächtigt, beabsichtigt zu haben, an unbekannten Orten in der Schweiz politisch motivierte Brandanschläge zu verüben. Zudem wird er dringend verdächtigt, in den Jahren 2007 und 2008 diverse Brandanschläge, allenfalls zusammen mit weiteren Tätern, bereits verübt zu haben.
Am 20. Januar 2009 wurde X._ festgenommen und am 22. Januar 2009 fand vor der Staatsanwaltschaft Zürich-Sihl die Hafteinvernahme statt. Am 23. Januar 2009 ordnete der Haftrichter des Bezirksgerichts Zürich die Untersuchungshaft an. In der Haftverfügung wurde vermerkt, dass der Beschwerdeführer auf eine persönliche Anhörung vor dem Haftrichter ausdrücklich verzichtet und auch sein Verteidiger bei der Hafteinvernahme keine solche verlangt habe.
B. X._ hat gegen die haftrichterliche Verfügung beim Bundesgericht Verfassungsbeschwerde eingelegt. Er beantragt, der angefochtene Entscheid sei aufzuheben, es sei festzustellen, dass Art. 31 Abs. 2 und 3 und <ref-law> sowie Art. 5 Ziff. 2 und 3 und Art. 6 Ziff. 1 EMRK verletzt worden seien, und er sei unverzüglich aus der Haft zu entlassen. Ferner ersucht der Beschwerdeführer um unentgeltliche Prozessführung im bundesgerichtlichen Verfahren.
C. Der Haftrichter hat auf Vernehmlassung verzichtet. Die zuständige Staatsanwältin der Staatsanwaltschaft Zürich-Sihl beantragt die Abweisung der Beschwerde, soweit sie die Staatsanwaltschaft Zürich-Sihl betreffe. Dem Beschwerdeführer ist die Frist zur Replik abgenommen worden.

Erwägungen:
1. Die Sachurteilsvoraussetzungen der Beschwerde in Strafsachen (<ref-law>) sind vorliegend grundsätzlich erfüllt. Das Rechtsmittel ist deshalb nicht als Verfassungsbeschwerde (vgl. <ref-law>), sondern als Beschwerde in Strafsachen entgegenzunehmen und zu behandeln.
2. 2.1 Der Beschwerdeführer rügt unter anderem eine Verletzung des rechtlichen Gehörs. Er macht geltend, vor Erlass der Haftverfügung vom 23. Januar 2009 habe er in Verletzung von Art. 29 Abs. 2 und <ref-law>, Art. 5 Ziff. 3 EMRK sowie § 61 der Strafprozessordnung des Kantons Zürich vom 4. Mai 1919 (StPO; LS 321) keine Gelegenheit gehabt, sich zum Haftantrag der Staatsanwältin zu äussern und Einsicht in die Akten zu nehmen.
2.2 Jede Person, die in Untersuchungshaft genommen wird, hat gestützt auf <ref-law> Anspruch darauf, unverzüglich einer Richterin oder einem Richter vorgeführt zu werden; die Richterin oder der Richter entscheidet, ob die Person weiterhin in Haft gehalten oder freigelassen wird. Aus <ref-law> (Art. 5 Ziff. 3 EMRK) fliesst das Recht des Beschuldigten auf persönlichen Anhörung im Haftanordnungsverfahren. A maiore minus ergibt sich daraus auch ein Anspruch auf schriftliche Stellungnahme vor dem Haftrichter. Ein Anspruch auf schriftliche Stellungnahme vor dem Haftrichter und Einsicht in die Haftakten ergibt sich überdies aus dem Anspruch auf rechtliches Gehör (<ref-law>). Das kantonale Recht kann über diese verfassungsrechtlichen Minimalgarantien hinausgehen (<ref-ruling> E. 2.1.1 S. 161).
Nach Zürcher Strafprozessrecht gibt der Haftrichter dem Angeschuldigten und seinem Verteidiger Gelegenheit, sich zu den Vorbringen der Untersuchungsbehörde zu äussern. Er gewährt ihnen Einsicht in die vom Untersuchungsbeamten unterbreiteten Akten. Der Angeschuldigte ist auf sein Verlangen persönlich anzuhören (<ref-law>). Diese Vorschrift beinhaltet somit ebenfalls drei Teilgehalte: das Recht auf schriftliche Stellungnahme, das Recht auf Akteneinsicht und das Recht auf persönliche Anhörung (vgl. ANDREAS DONATSCH, in: Donatsch/Schmid (Hrsg.), Kommentar zur Strafprozessordnung des Kantons Zürich, 1996, N. 7 zu § 61). Der Angeschuldigte kann auf diese Rechte verzichten (vgl. DONATSCH, a.a.O., N. 9 zu <ref-law>). Jedoch bedeutet der Verzicht auf einen Teilgehalt von <ref-law>, etwa der Verzicht auf persönliche Anhörung vor dem Haftrichter, nicht notwendigerweise auch ein Verzicht auf Einsicht in die Haftakten und auf schriftliche Stellungnahme zum Haftantrag der Staatsanwaltschaft.
2.3 Der Rechtsanwalt des Beschwerdeführers schildert den Verfahrensablauf wie folgt: Anlässlich der staatsanwaltschaftlichen Einvernahme vom 22. Januar 2009 habe die für den Fall zuständige Staatsanwältin angekündigt, dass sie einen Antrag auf Anordnung der Untersuchungshaft beim Haftrichter des Bezirksgerichts Zürich einreichen werde. Als Anwalt des Beschwerdeführers sei er bei der Einvernahme ebenfalls anwesend gewesen. Dabei sei ihm in Aussicht gestellt worden, dass er beim Haftrichter Akteneinsicht nehmen könne. Der Beschwerdeführer habe zuerst beantragt, durch den Haftrichter angehört zu werden. Als ihm jedoch erklärt worden sei, dass sein Rechtsanwalt beim Haftrichter schriftlich zum Haftantrag Stellung nehmen könne, habe der Beschwerdeführer auf eine persönliche Anhörung verzichtet. Sowohl der Beschwerdeführer als auch er als sein Rechtsanwalt hätten angekündigt, dass er bei Vorliegen des staatsanwaltschaftlichen Haftantrags und nach Einsicht in die Akten zum betreffenden Antrag Stellung nehmen würde.
Noch am gleichen Tag habe er als Rechtsvertreter des Beschwerdeführers das Haftrichteramt angerufen und erklärt, dass er Einsicht in die Akten wünsche. Da die zuständige juristische Sekretärin abwesend gewesen sei, habe man ihm versprochen, Abklärungen zu treffen und ihn telefonisch zu unterrichten. Eine solche Information sei am 22. Januar 2009 aber nicht erfolgt.
Am folgenden Tag, dem 23. Januar 2009, habe er sich beim Haftrichteramt erneut telefonisch erkundigt, ob er als Verteidiger Akteneinsicht nehmen könne. Die zuständige juristische Sekretärin habe ihm daraufhin erklärt, der Haftrichter habe den Entscheid bereits gefällt, er könne keine Akteneinsicht mehr nehmen und solle sich für die Akteneinsicht an die zuständige Staatsanwältin wenden. Erst am 26. Januar 2009 sei ihm die Möglichkeit zur Akteneinsicht eingeräumt worden.
Diese Sachverhaltsdarstellung wird weder von der Staatsanwaltschaft noch vom Haftrichter in Frage gestellt. Aktenwidrig ist aber die Behauptung des Rechtsvertreters, er habe erst nach dem 26. Januar 2009 vom schriftlich begründeten Antrag auf Anordnung der Untersuchungshaft Kenntnis nehmen können (vgl. Beschwerde S. 9). Der vom 22. Januar 2009 datierende, schriftlich begründete Haftantrag enthält auf Seite 3 die Unterschrift des Beschwerdeführers, womit dieser einerseits auf persönliche Anhörung vor dem Haftrichter verzichtete und andererseits bestätigte, ein gleichlautendes Doppel des Haftantrags erhalten zu haben. Die Unterschrift des Beschwerdeführers datiert ebenfalls vom 22. Januar 2009. Der Rechtsanwalt des Beschwerdeführers war, wie oben erwähnt, an der Hafteinvernahme vom 22. Januar 2009 anwesend.
2.4 Dem Gesagten zufolge verzichtete der Beschwerdeführer unterschriftlich auf persönliche Anhörung vor dem Haftrichter. Dieser Verzicht beinhaltete aber nicht auch den Verzicht auf schriftliche Stellungnahme und Einsicht in die Haftakten durch den Rechtsverteidiger des Beschwerdeführers. Ein solcher Verzicht liesse sich aus der Formulierung des Verzichts auf Seite 3 des Haftantrags ("Ich verzichte ausdrücklich auf eine Anhörung durch den Haftrichter.") jedenfalls nicht ableiten. Im Gegenteil äusserte sich der Rechtsanwalt des Beschwerdeführers gemäss unbestritten gebliebenen Behauptungen mehrmals dahingehend, zum Haftantrag schriftlich Stellung nehmen und vorgängig Akteneinsicht nehmen zu wollen. Der Haftrichter hätte den Entscheid über die Anordnung der Untersuchungshaft deshalb nicht treffen dürfen, ohne dem Beschwerdeführer resp. seinem Rechtsvertreter vorgängig die Gelegenheit eingeräumt zu haben, sich zum Haftantrag der Staatsanwaltschaft schriftlich zu äussern und Einsicht in die Haftakten zu nehmen. Aufgrund dieser Unterlassung hat der Haftrichter die Rechte des Angeschuldigten aus <ref-law> resp. dessen Anspruchs auf rechtliches Gehör (Art. 31 Abs. 3 und <ref-law>) verletzt. Die Beschwerde erweist sich in diesem Punkt als begründet. Die Prüfung der weiteren Rügen erübrigt sich.
3. Die Beschwerde ist somit gutzuheissen, die angefochtene Verfügung aufzuheben und die Sache zu neuem Entscheid an die Vorinstanz zurückzuweisen. Das Gesuch um sofortige Haftentlassung ist abzuweisen. Ausgangsgemäss werden keine Gerichtskosten erhoben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Das Gesuch um unentgeltliche Prozessführung wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird als Beschwerde in Strafsachen entgegengenommen.
2. Die Beschwerde wird gutgeheissen, die Verfügung vom 23. Januar 2009 des Haftrichters des Bezirksgerichts Zürich aufgehoben und die Sache zu neuem Entscheid an den Haftrichter zurückgewiesen.
3. Das Haftentlassungsgesuch wird abgewiesen.
4. Es werden keine Gerichtskosten erhoben.
5. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
6. Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft Zürich-Sihl und dem Bezirksgericht Zürich, Haftrichter, schriftlich mitgeteilt.
Lausanne, 16. Februar 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Schoder