Faits:
A. L._ a été au bénéfice d'un délai-cadre d'indemnisation de l'assurance-chômage depuis le 21 mai 2007.
Par lettre du 6 janvier 2009, le Service des mesures cantonales (SMC) de Genève a constaté que l'assurée ne lui avait pas fait parvenir ses recherches personnelles d'emploi du mois de décembre 2008 dans le délai prévu par la loi (5 janvier 2009); il lui a fixé un délai supplémentaire échéant le 13 janvier 2009, en attirant son attention sur le fait que si ce délai n'était pas respecté, lesdites recherches d'emploi ne pourraient pas être prises en compte et, partant, seraient considérées comme nulles.
Par décision du 16 janvier 2009, le SMC a suspendu, pour une durée de cinq jours, le droit de L._ aux indemnités de chômage, au motif que celle-ci n'avait justifié d'aucune recherche personnelle d'emploi pour le mois de décembre 2008.
Le formulaire de recherches d'emploi relatif à ce mois, daté du 15 janvier 2009, a été reçu par le SMC le 19 janvier 2009 selon le tampon apposé sur le document.
L'assurée s'est opposée à la décision du 16 janvier 2009. Elle faisait valoir qu'elle avait envoyé une liste de recherches d'emploi le 22 décembre 2008 à l'Office régional de placement (ORP) nonobstant le fait qu'elle était en vacances du 17 décembre 2008 au 5 janvier 2009. Elle a précisé qu'à réception du courrier de rappel du SMC le 9 janvier 2009, elle avait expédié le formulaire une seconde fois le 16 janvier 2009 à cet office.
Par décision sur opposition du 24 février 2009, l'Office cantonal de l'emploi (OCE) a confirmé la décision du SMC du 16 janvier 2009. Il a considéré que l'assurée n'avait pas apporté la preuve qu'elle avait envoyé ses recherches d'emploi relatives au mois de décembre 2008 dans le délai réglementaire (5 janvier 2009) et qu'elle n'avait pas non plus respecté le délai supplémentaire fixé au 13 janvier 2009.
B. L._ a recouru contre la décision sur opposition du 24 février 2009 devant le Tribunal cantonal des assurances sociales de la République et canton de Genève. Lors de son audition par la juridiction cantonale, elle a exposé qu'elle avait été suivie, jusqu'à la fin de l'année 2008, par une conseillère à Y._. Lors du dernier entretien, celle-ci lui avait annoncé qu'elle arrivait en fin de période et que le SMC prendrait contact avec elle. Elle n'avait pas compris qu'à partir de ce moment, la conseillère ne s'occuperait plus de son dossier, raison pour laquelle elle lui avait adressé ses recherches d'emploi de décembre. Elle avait réalisé que son dossier avait été transféré au SMC seulement à réception du courrier de rappel du SMC. Par ailleurs, l'assurée a précisé que durant le mois de décembre 2008, elle avait effectué bien plus de recherches d'emploi que celles mentionnées dans le formulaire. En outre, une de ses démarches avait débouché sur l'emploi qu'elle occupe actuellement auprès de X._.
Par jugement du 28 mai 2009, la juridiction cantonale a admis le recours et annulé les décisions précédentes.
C. L'OCE interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation.
L'intimée conclut au rejet du recours, alors que le Secrétariat d'Etat à l'économie a renoncé à se déterminer.

Considérant en droit:
1. Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit au sens des art. 95 et 96 LTF. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Cette disposition lui donne la faculté de rectifier ou compléter d'office l'état de fait de l'arrêt attaqué dans la mesure où des lacunes ou erreurs dans l'établissement de celui-ci lui apparaîtraient d'emblée comme manifestes.
Quant au recourant, il ne peut critiquer la constatation de faits importants pour le jugement de la cause que si ceux-ci ont été constatés en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte (<ref-law>).
2. Le litige porte sur le point de savoir si l'OCE était fondé, par sa décision sur opposition du 24 février 2009, à suspendre le droit de l'intimée à l'indemnité de chômage pour une durée de cinq jours, motif pris qu'elle n'avait pas remis en temps utile les justificatifs de recherches d'emploi pour le mois de décembre 2008.
3. Le jugement entrepris présente les dispositions légales relatives à la suspension du droit aux indemnités de chômage et à l'obligation des assurés d'apporter la preuve de leurs efforts en vue de retrouver un emploi. Sur ces points, il convient d'y renvoyer.
On rappellera, cependant, qu'en s'inscrivant pour toucher des indemnités, l'assuré doit fournir à l'office compétent la preuve des efforts qu'il entreprend pour trouver du travail (<ref-law>). Par ailleurs, il doit apporter cette preuve pour chaque période de contrôle en remettant ses justificatifs au plus tard le cinq du mois suivant ou le premier jour ouvrable qui suit cette date. S'il ne les a pas remis dans ce délai, l'office compétent lui impartit un délai raisonnable pour le faire. Simultanément, il l'informe par écrit qu'à l'expiration de ce délai et en l'absence d'excuse valable, les recherches d'emploi ne pourront pas être prises en considération (<ref-law>). On précisera également que l'<ref-law> a été reconnu conforme à la loi (<ref-ruling>; voir aussi arrêt 8C_183/ 2008 du 27 juin 2008 consid. 3 in DTA 2009 p. 76).
4. La juridiction cantonale a considéré que l'intimée avait établi avec suffisamment de vraisemblance qu'elle avait envoyé la liste de ses recherches d'emploi pour le mois de décembre 2008, le 22 décembre 2008. L'OCE affirmait certes qu'aucune trace du courrier en question n'avait été retrouvée à l'agence de Y._. Cependant, l'assurée avait toujours rempli ses obligations en temps utile. La perte du courrier apparaissait d'autant plus vraisemblable que celui-ci aurait dû être adressé au SMC: le fait que le dossier était clôturé chez le destinataire augmentait les chances qu'il s'égare. Enfin, le flux important d'échanges auquel la Poste devait faire face en période de fêtes de fin d'année contribuait également à accroître le risque que le courrier de l'assurée ne se perde. Certes, celle-ci n'avait pas respecté le délai supplémentaire qui lui avait été imparti. Cependant, au vu de l'ensemble des circonstances particulières du cas, il paraissait disproportionné d'infliger une telle sanction à l'assurée pour ce premier manquement.
5. 5.1 L'office recourant fait grief à la juridiction cantonale d'avoir méconnu la portée de l'<ref-law>, en considérant l'envoi du formulaire de recherches comme hautement vraisemblable. Se référant à la jurisprudence du Tribunal fédéral (arrêt C 3/07 du 3 janvier 2008), il estime que le respect du délai prévu par cette disposition aurait dû être déterminé avec certitude.
5.2 Il est douteux que le faisceau d'indices sur lequel s'est fondée la juridiction cantonale suffise à établir que l'intimée a fourni en temps utile (soit jusqu'au 5 janvier 2009) ses justificatifs de recherches d'emploi. L'intéressée a déclaré avoir envoyé ses recherches du mois de décembre 2008 le 22 décembre 2008. Toutefois, cet envoi n'est pas parvenu à son ancienne conseillère en placement, ni au SMC, auquel le dossier a été transféré. Par ailleurs, ainsi que l'expose l'office recourant, dans l'hypothèse où le courrier serait parvenu à une personne qui aurait été déchargée du dossier, le pli ne se serait pas perdu: on peut penser qu'il aurait été acheminé à son nouveau titulaire dans un intervalle de deux à trois jours. On ajoutera que le seul fait que l'assurée a toujours rempli ses obligations n'est pas un indice suffisant.
5.3 Quoi qu'il en soit, l'assurée n'a pas respecté le délai supplémentaire (fixé au 13 janvier 2009) pour remettre ses recherches d'emploi, alors même qu'elle avait été avertie par écrit qu'en l'absence d'excuse valable, les recherches ne pourraient pas être prises en considération. Or, il était raisonnablement exigible, après ce rappel et l'avertissement relatif aux conséquences d'un retard, qu'elle s'assure, le cas échéant, de pouvoir prouver l'envoi de la liste de ses recherches en temps utile. L'intimée fait certes valoir qu'elle a reçu la lettre de rappel du SMC à une date postérieure au 13 janvier 2009, si bien qu'elle ne pouvait plus réagir dans le délai imparti. Or, ces allégations sont en contradiction avec les déclarations qu'elle a faites dans son opposition selon lesquelles elle a reçu le courrier de rappel le 9 janvier 2009. Dans une telle situation, il y a lieu, conformément à la jurisprudence (<ref-ruling> consid. 2a p. 47 et les références) de se baser sur les premières déclarations de l'assurée. On doit ainsi considérer que rien n'empêchait l'intimée d'expédier, dans le délai supplémentaire, la liste de ses recherches d'emploi, comme elle l'a fait, mais tardivement. Dans ces conditions, le SMC pouvait faire abstraction de ses recherches d'emploi pour décembre 2008 et, par conséquent, suspendre son droit à l'indemnité de chômage (art. 30 al. 1 let. c LACI).
6. En ce qui concerne la quotité de la sanction, fixée à cinq jours par le SMC, elle ne prête pas le flanc à la critique (cf. <ref-law>).
7. Il suit de là que le recours est bien fondé. L'intimée, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et le jugement du 28 mai 2009 du Tribunal cantonal des assurances sociales de la République et canton de Genève est annulé.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimée.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal des assurances sociales de la République et canton de Genève et au Secrétariat d'Etat à l'économie.
Lucerne, le 26 février 2010
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Ursprung Berset