Faits:
A. Dans le cadre d'une poursuite n° xxx dirigée par X._(ci-après: le créancier) contre Y._ (ci-après: le débiteur), l'Office des poursuites de Genève a fait notifier à ce dernier une commination de faillite le 2 septembre 2008. Le 8 du même mois, le débiteur a porté plainte contre cet acte auprès de la Commission de surveillance des offices des poursuites et des faillites du canton de Genève. Il affirmait, d'une part, n'avoir jamais reçu notification du commandement de payer de la poursuite en cause et contestait, d'autre part, sa qualité de débiteur.
L'office a informé la commission de surveillance que, selon l'exemplaire pour le créancier du commandement de payer, cet acte avait été notifié en mains du débiteur, qui n'avait pas formé opposition, le 18 juin 2008. Il a en outre produit un courrier du responsable de PostLogistics pour les actes de poursuite, à teneur duquel, notamment, la notification en cause avait été effectuée au domicile du débiteur par l'employée Z._ (ci-après: la notificatrice), qui avait eu alors « la certitude d'avoir en face d'elle le débiteur lui-même ».
B. Dans le cadre de l'instruction de la plainte, la commission de surveillance a notamment entendu la notificatrice (à deux reprises) en qualité de témoin, ainsi que le débiteur et son épouse, cette dernière à titre de renseignement.
Par décision du 11 décembre 2008, la commission de surveillance a, quant à la forme, déclaré la plainte partiellement recevable, soit en tant qu'elle portait sur la notification du commandement de payer, la question de la justification de la créance en poursuite échappant à sa compétence; quant au fond, elle a admis la plainte et annulé la notification du commandement de payer.
L'autorité cantonale a retenu, en bref, qu'il n'était pas établi à satisfaction de droit, au vu des affirmations du plaignant et des déclarations de la notificatrice, que le commandement de payer avait bien été notifié le 18 juin 2008 en mains de son destinataire et donc que l'attestation de cette notification était exacte. Le débiteur avait en outre agi en temps utile en déposant plainte dans le délai de dix jours dès réception de la commination de faillite, puisqu'il avait eu alors la possibilité d'avoir une connaissance effective du commandement de payer et de sa teneur exacte. Il s'ensuivait que la plainte devait être admise et la notification du commandement de payer annulée.
C. Contre la décision de la commission cantonale de surveillance, qui lui a été notifiée le 15 décembre 2008, le créancier a interjeté un recours en matière civile au Tribunal fédéral le 12 janvier 2009, concluant principalement à l'annulation de la décision attaquée et au rejet de la plainte du débiteur, subsidiairement au renvoi de la cause à l'autorité cantonale pour nouvelle décision dans le sens des considérants. Le recourant invoque un établissement manifestement inexact des faits au sens de l'<ref-law> et une violation du droit fédéral au sens de l'<ref-law>, soit de l'interdiction de l'arbitraire (art. 9 Cst.) et des règles sur la foi des registres publics (<ref-law>) et sur la notification des actes de poursuite (<ref-law>).
Le dépôt d'une réponse n'a pas été requis.

Considérant en droit:
1. Le recours a été interjeté dans le délai de dix jours prévu par l'<ref-law>, compte tenu des dispositions sur la suspension des délais (art. 46 al. 1 let. c LTF) et leur fin (<ref-law>), ainsi que dans la forme requise par la loi (<ref-law>). Il émane d'une partie qui a succombé dans ses conclusions prises devant l'autorité précédente (<ref-law>) et il est dirigé contre une décision finale (<ref-law>) rendue en matière de poursuite pour dettes et de faillite (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>). Le recours est donc recevable en principe (cf. <ref-ruling> consid. 1.2), indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF).
2. 2.1 La commission cantonale de surveillance a conclu au défaut d'une notification dûment établie du commandement de payer en mains du débiteur le 18 juin 2008 sur la base des constatations suivantes: le débiteur avait affirmé qu'aucun acte de poursuite ne lui avait été remis ce jour-là, que, quittant son appartement tous les matins à 6 h 30 pour commencer son travail à 7 heures, il ne s'expliquait pas la présence, dans son logement, de l'homme dont la notificatrice faisait état et qu'il n'avait jamais rencontré cette dernière; son épouse avait dit ne pas se rappeler qu'en juin 2008 une employée de La Poste aurait sonné à la porte de son domicile; des déclarations de la notificatrice, il ressortait que cette dernière s'était souvenue du débiteur, car il lui avait « bien fallu quelque cinq minutes pour remplir les deux commandements de payer » qu'elle lui avait notifiés le 18 juin 2008; elle avait par ailleurs affirmé qu'avant cette date elle ne l'avait jamais rencontré et avait précisé qu'elle avait dû lui notifier des commandements de payer auparavant, mais qu'elle n'avait pas pu les lui remettre en mains propres et avait laissé des avis de retrait dans sa boîte aux lettres; il s'avérait toutefois que cette même notificatrice avait, en date du 30 avril 2008, notifié un commandement de payer au débiteur, qui n'avait pas fait opposition, et que cet acte, au vu des mentions y figurant, avait été remis au débiteur « en personne », ce que ce dernier contestait. Il s'ensuivait, selon la commission de surveillance, que soit la notificatrice n'avait jamais notifié d'actes de poursuite en mains du débiteur, ce que ce dernier affirmait, soit elle lui avait notifié trois commandements de payer, un le 30 avril 2008 et deux le 18 juin 2008; or, la notificatrice avait formellement déclaré qu'elle n'avait jamais vu le débiteur avant le 18 juin 2008 et qu'elle n'avait pu lui remettre les actes de poursuite antérieurs qui lui étaient destinés; les déclarations de la notificatrice étaient donc contredites par le procès-verbal de notification du 30 avril 2008.
2.2 De jurisprudence constante, le Tribunal fédéral se montre réservé en matière de constatation des faits et d'appréciation des preuves, vu le large pouvoir qu'il reconnaît en ce domaine aux juridictions cantonales (<ref-ruling> consid. 4b p. 40; <ref-ruling> consid. 9 p. 399 et les arrêts cités). Il n'intervient, du chef de l'art. 9 Cst., que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans raisons objectives de tenir compte de preuves pertinentes ou a effectué, sur la base des éléments recueillis, des déductions insoutenables; encore faut-il que la décision attaquée en soit viciée dans son résultat (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41; cf. aussi <ref-ruling> consid. 1.4.3 p. 254/255).
2.3 A l'appui de son grief d'établissement inexact des faits, le recourant reprend différentes déclarations faites par la notificatrice, le débiteur et son épouse devant l'autorité précédente et conclut qu'au vu de ces déclarations, « il est clair que la Commission de surveillance a établi les faits de façon manifestement inexacte », l'analyse desdites déclarations ayant dû la convaincre que le commandement de payer litigieux avait bien été notifié au débiteur. Ce faisant, le recourant n'indique pas en quoi précisément l'autorité cantonale aurait constaté inexactement les faits en question; il lui reproche en revanche d'avoir effectué une mauvaise déduction de ceux-ci; il trouve surprenant qu'elle ait remis en cause les déclarations de la notificatrice plutôt que celles, à son avis peu claires et peu fiables, du débiteur, et ce sur un seul et unique élément où elle s'était trompée, à savoir le fait que la première fois qu'elle avait rencontré le débiteur fut le 18 juin 2008, alors qu'en réalité elle lui avait déjà notifié un commandement de payer le 30 avril 2008.
La preuve de la notification régulière des actes de poursuite incombant en première ligne à l'office (<ref-ruling>; <ref-ruling> consid. 5c; <ref-ruling> consid. 2), les déclarations de la personne chargée de la notification l'emportent naturellement sur celles du destinataire de l'acte, dont on ne saurait d'ailleurs exiger qu'il prouve le fait - négatif - de l'absence de notification. En l'espèce, l'autorité cantonale devait donc tenir compte en priorité des déclarations de la notificatrice. Or, il est constant que celle-ci s'est contredite sur un point décisif en affirmant n'avoir jamais vu le débiteur avant le 18 juin 2008, alors que le 30 avril précédent, selon procès-verbal de notification dressé à cette date, elle lui avait « notifié en personne » un premier commandement de payer. Au vu de cette contradiction, il n'était pas insoutenable de retenir comme non établi à satisfaction de droit le fait que le commandement de payer ici en cause avait bien été notifié le 18 juin 2008 en mains du débiteur, ce d'autant que ce dernier avait déclaré que plusieurs membres de sa famille ainsi que des amis passaient régulièrement chez lui, que ses deux neveux ainsi que le frère de son épouse étaient venus leur rendre visite plusieurs fois entre les mois de mai et juillet 2008 et qu'ils avaient passé quelques jours auprès d'eux.
Le grief d'établissement inexact des faits s'avère donc mal fondé.
3. Selon la jurisprudence, le recourant qui se plaint d'arbitraire (art. 9 Cst.) ne peut se contenter de critiquer la décision attaquée comme il le ferait en instance d'appel, où la juridiction supérieure jouit d'une libre cognition; en particulier, il ne saurait se limiter à opposer son opinion à celle de l'autorité cantonale, mais il doit démontrer par une argumentation précise que cette décision se fonde sur une application de la loi ou une appréciation des preuves manifestement insoutenables (cf. <ref-ruling> consid. 2.1 p. 120; <ref-ruling> consid. 7a p. 312; <ref-ruling> consid. 1b p. 495 et les arrêts cités).
En l'espèce, le recourant ne fait pas une telle démonstration à l'appui de son grief d'arbitraire. Contrairement à ce qu'il prétend, l'autorité cantonale ne s'est pas fondée, ainsi que cela ressort clairement du considérant précédent, sur le simple fait que le débiteur ait pu dire que le commandement de payer ne lui avait pas été notifié.
Il s'ensuit que le grief d'arbitraire doit être rejeté dans la mesure de sa recevabilité.
4. L'<ref-law> prévoit que les registres publics et les titres authentiques font foi des faits qu'ils constatent et dont l'inexactitude n'est pas prouvée.
Le procès-verbal de notification du commandement de payer selon l'<ref-law> est un titre public au sens de l'<ref-law> (<ref-ruling> consid. 2; <ref-ruling> consid. 5c et les références). L'attestation sur le commandement de payer administre donc, en principe, la preuve de la notification, mais les parties ont le droit de rapporter la preuve contraire (<ref-ruling> consid. 2). Il est cependant de règle en cette matière que, si le procès-verbal est lacunaire ou s'il y a contestation, c'est l'office qui supporte en première ligne le fardeau de la preuve de la notification régulière (ATF 120 et 117 III précités; <ref-ruling> consid. 2).
En l'espèce, l'indication figurant sur le commandement de payer selon laquelle la notification a eu lieu en mains propres du débiteur est contestée. C'est dès lors en vain, en vertu de la règle précitée, que le recourant allègue qu'il aurait appartenu au débiteur d'apporter la preuve de l'inexactitude de ladite attestation.
5. L'<ref-law>, dont le recourant invoque également la violation, prévoit notamment que les actes de poursuite sont notifiés au débiteur dans sa demeure et, s'il est absent, à une personne adulte de son ménage. Dans le cas particulier, si la notification du commandement de payer litigieux a bien eu lieu au domicile du débiteur, il n'est pas établi à satisfaction de droit, selon les constatations non arbitraires de la décision attaquée (cf. consid. 2 ci-dessus), que ledit acte lui a été remis en mains propres ou à quelqu'autre personne adulte de son ménage. Contrairement à ce que soutient le recourant, l'autorité cantonale a donc eu raison d'admettre la plainte et d'annuler la notification litigieuse pour ce motif.
6. Il résulte de ce qui précède que le recours doit être rejeté dans la mesure de sa recevabilité, aux frais de son auteur (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 1'500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et à la Commission de surveillance des offices des poursuites et des faillites du canton de Genève.
Lausanne, le 18 mars 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Hohl Fellay