Sachverhalt:
A. A.a Mit Entscheid vom 30. Januar 2009 erteilte die Amtsgerichtspräsidentin II von Sursee in der gegen X._ laufenden Betreibung Nr. .../BA A._ der Z._ AG (nachfolgend Beschwerdegegnerin) für den Betrag von Fr. 7'071.95 die provisorische Rechtsöffnung.
A.b Dagegen erhob X._ (nachfolgend Beschwerdeführer) am 4. März 2009 Nichtigkeitsbeschwerde bei der Schuldbetreibungs- und Konkurskommission des Obergerichts des Kantons Luzern. Am 9. März 2009 wurde der Beschwerdeführer aufgefordert, bis Freitag, 20. März 2009 einen Kostenvorschuss von Fr. 350.-- zu bezahlen. Die Überweisung erfolgte am 22. März 2009. Mit Eingabe vom 23. März 2009 teilte der Beschwerdeführer dem Obergericht mit, er habe am 20. März 2009 per e-Banking den Kostenvorschuss bezahlen wollen, wobei ein Fehler in der Verbindung aufgetreten sei, den er erst am 22. März 2009 erkannt und deshalb die Zahlung erst an diesem Tag vorgenommen habe.
A.c Am 30. März 2009 setzte der Präsident der Schuldbetreibungs- und Konkurskommission dem Beschwerdeführer Frist, bis zum 7. April 2009 dem Obergericht den Beweis zu erbringen, dass er den Auftrag rechtzeitig erteilt habe, dieser aber aus Gründen, die nicht in seiner Verantwortung lägen, nicht habe ausgeführt werden können.
Da der Beschwerdeführer hierauf nicht reagiert hatte, trat das Obergericht mit Entscheid vom 23. April 2009 auf die Nichtigkeitsbeschwerde nicht ein.
A. Der Beschwerdeführer hat mit einer als "Beschwerde gegen Verfahrensfehler" bezeichneten Eingabe vom 3. Juni 2009 die Sache an das Bundesgericht weitergezogen und beantragt, den angefochtenen Entscheid aufzuheben und das Verfahren einzustellen.
Das Obergericht schliesst in seiner Vernehmlassung, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Beschwerdegegnerin hat auf Stellungnahme verzichtet.
Die Sache wurde an einer publikumsöffentlichen Sitzung entschieden.

Erwägungen:
1. 1.1 Gemäss <ref-law> unterliegen der Beschwerde in Zivilsachen auch Entscheide in Schuldbetreibungs- und Konkurssachen. Beim vorliegenden Entscheid über die provisorische Rechtsöffnung handelt es sich um einen solchen Entscheid. Da der Streitwert von mindestens 30'000 Franken (<ref-law>) nicht erreicht wird, ist gegen den letztinstanzlichen Endentscheid somit nur die subsidiäre Verfassungsbeschwerde nach <ref-law> zulässig.
1.2 Mit der Verfassungsbeschwerde kann die Verletzung verfassungsmässiger Rechte gerügt werden (<ref-law>). Nach der gemäss <ref-law> auch für dieses Verfahren geltenden Bestimmung von <ref-law> prüft das Bundesgericht die Verletzung von Grundrechten nur insofern, als eine Rüge in der Beschwerde vorgebracht und begründet worden ist. Das bedeutet, dass - entsprechend den altrechtlichen Begründungsanforderungen von Art. 90 Abs. 1 lit. b OG - klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 6 S. 397).
2. 2.1 Der Beschwerdeführer rügt, die vom Obergericht angesetzten Fristen hätten von ihm unmöglich gewahrt werden können: Dieses habe ihn mit Schreiben vom 30. März 2009 aufgefordert, bis 7. April 2009 zu begründen, warum der Zahlungsauftrag nicht rechtzeitig habe ausgeführt werden können. Die Frist zur Abholung dieses Briefes bei der Post in A._ habe ebenfalls bis zum 7. April 2009 gedauert, und an diesem Tag habe er ihn dort um 17.30 Uhr in Empfang genommen. Eine Stellungnahme innert der ihm gesetzten Frist habe somit nicht erfolgen können. Damit wird sinngemäss eine Verletzung des rechtlichen Gehörs gerügt.
2.2 Die Vorinstanz führt in ihrer Vernehmlassung aus, im Regelfall werde die Abholfrist von sieben Tagen nicht voll ausgenutzt. Praxisgemäss würden eher kurze Fristen angesetzt, um das Verfahren nicht zu verzögern. Im Fall, da der Ablauf der Frist mit der Kenntnisnahme derselben zusammenfalle, könne der Betroffene gemäss <ref-law>/LU Wiederherstellung der Frist verlangen und innert 10 Tagen die versäumte Handlung nachholen. Deshalb sei mit der Fällung des Entscheids bis zum 23. April 2009 zugewartet worden, obwohl die eingeräumte Frist bereits am 7. April 2009 abgelaufen gewesen sei.
2.3 Gemäss dem "Track & Trace"-Auszug der Schweizerischen Post traf das Schreiben des Präsidenten der Schuldbetreibungs- und Konkurskommission vom 30. März 2009 am 31. März 2009 auf der Post A._ ein, wurde am gleichen Tag zur Abholung gemeldet und am 7. April 2009 dem Beschwerdeführer am Schalter zugestellt. Das Ende der Äusserungsfrist fiel im vorliegenden Fall mit dem letzten Tag der Abholfrist zusammen.
Die Vorinstanz rechtfertigt ihren Entscheid unter anderem mit dem Hinweis auf das Beschleunigungsgebot. Gemäss <ref-law> gibt der Rechtsöffnungsrichter dem Betriebenen sofort nach Eingang des Gesuches Gelegenheit zur mündlichen oder schriftlichen Stellungnahme und eröffnet danach innert fünf Tagen seinen Entscheid. Bei dieser Bestimmung handelt es sich um eine blosse Ordnungsvorschrift und das Bundesgericht hat bereits in einem älteren Urteil festgehalten, diese müsse zurücktreten, wenn durch ihre Einhaltung den Parteien unter Umständen das rechtliche Gehör verweigert würde (Urteil des Bundesgerichts 5A_151/2007 vom 22. Januar 2008, E. 3.2 mit Hinweis auf <ref-ruling> E. 3 S. 468). Im zuletzt zitierten Urteil wird weiter ausgeführt (S. 467 f.), der rechtsunkundige Bürger, der von der Post eine eingeschriebene Mitteilung mit einer Abholfrist von 7 Tagen erhalte, müsse sich darauf verlassen können, dass ihm diese Frist tatsächlich zur Verfügung stehe. Auch die Rechtssicherheit verlange eine klare, allgemein verständliche und einheitliche Regelung, wann eine eingeschriebene Postsendung als zugestellt zu gelten habe. Diese Grundsätze seien deshalb auch im Rechtsöffnungsverfahren anzuwenden. An dieser Rechtsprechung ist festzuhalten. Im vorliegenden Fall wurde mit der Fristansetzung zur Stellungnahme auf den Tag, an dem der Zeitpunkt zur Abholung der Mitteilung endete, dem Beschwerdeführer das rechtliche Gehör verweigert. Das hätte das Obergericht vermeiden können, indem es zum Beispiel eine nach Tagen bestimmte (angemessene) Frist ab Empfang der Mitteilung angesetzt hätte. Eine derartige Vorgehensweise hätte auch keine nennenswerte Verzögerung des Verfahrens bewirkt.
1. Nach dem Gesagten muss die Verfassungsbeschwerde gutgeheissen, der angefochtene Entscheid aufgehoben und zwecks Gewährung des rechtlichen Gehörs an die Vorinstanz zurückgewiesen werden. Dem Kanton Luzern dürfen als unterliegender Partei keine Gerichtskosten auferlegt werden (<ref-law>). Dem Beschwerdeführer ist keine Parteientschädigung zuzusprechen, da er nicht anwaltlich vertreten war (<ref-ruling> E. 4 S. 446).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Obergerichts des Kantons Luzern, Schuldbetreibungs- und Konkurskommission, vom 23. April 2009 wird aufgehoben.
2. Die Sache wird an das Obergericht zu neuer Entscheidung im Sinne der Erwägungen zurückgewiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Es wird keine Parteientschädigung zugesprochen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, Schuldbetreibungs- und Konkurskommission, als Beschwerdeinstanz, schriftlich mitgeteilt.
Lausanne, 3. September 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Schett