Faits:
A. D._ s'est inscrit comme demandeur d'emploi à l'Office régional de placement de Genève (ci-après : ORP), le 31 janvier 2006. Il a par la suite régulièrement perçu des indemnités journalières de chômage. Par lettre du 6 avril 2006, l'ORP lui a rappelé qu'il n'avait pas encore remis une liste de ses recherches d'emploi pour le mois de mars 2006 et l'a invité à le faire dans un délai échéant le 13 avril suivant; à défaut, il encourait une mesure de suspension de son droit aux indemnités journalières.
Par décision du 26 avril 2006, l'ORP a suspendu, pour une durée de cinq jours, le droit de D._ aux indemnités journalières de chômage, au motif que celui-ci n'avait toujours pas remis de liste de ses recherches d'emploi pour mars 2006, malgré la lettre de rappel du 6 avril 2006. Le 2 mai 2006, D._ a écrit à sa conseillère en placement à l'ORP qu'il avait envoyé une liste de ses recherches d'emploi pour le mois de mars 2006 conformément à la demande du 6 avril 2006 et qu'un problème de secrétariat avait dû se produire. L'assuré a joint à sa lettre une copie de la liste en question. Le 5 mai 2006, il s'est opposé à la décision de suspension du droit aux indemnités journalières, en précisant avoir adressé à l'ORP, le 7 avril 2006, une liste de ses recherches d'emploi pour le mois de mars. L'Office cantonal de l'emploi (ci-après : OCE) a maintenu la mesure de suspension, par décision sur opposition du 8 juin 2006. Selon cette décision, renseignements pris auprès de l'ORP, aucun formulaire de preuves de recherches personnelles d'emploi relatif au mois de mars 2006 ne figurait au dossier de l'assuré jusqu'à l'envoi de sa lettre du 2 mai 2006.
B. D._ a recouru contre la décision sur opposition du 8 juin 2006 devant le Tribunal des assurances sociales du canton de Genève. Lors de son audition par la juridiction cantonale, il a exposé qu'il avait, dans un premier temps, conservé son dossier pour le soumettre à sa conseillère en placement lors d'un entretien prévu le 15 mai 2006. En recevant le rappel du 6 avril 2006, il avait immédiatement envoyé la liste de ses recherches d'emploi pour le mois de mars 2006, sous pli simple. Il y avait apposé une mention afin que sa conseillère en placement l'appuie dans ses démarches pour trouver un poste de réadapteur/formateur à l'Office cantonal de l'assurance-invalidité. Il avait donc tout intérêt à envoyer sa lettre en temps utile.
Par jugement du 7 novembre 2006, le Tribunal des assurances sociales du canton de Genève a admis le recours et annulé la mesure de suspension litigieuse.
C. L'OCE a interjeté un recours contre ce jugement, dont il demande l'annulation. L'intimé conclut au rejet du recours, alors que le Secrétariat d'Etat à l'économie (Seco) a renoncé à se déterminer.

Considérant en droit:
1. La loi sur le Tribunal fédéral du 17 juin 2005 (LTF; RS 173.110) est entrée en vigueur le 1er janvier 2007 (RO 2006 1205, 1242). L'acte attaqué ayant été rendu avant cette date, la procédure reste régie par l'OJ (art. 132 al. 1 LTF; <ref-ruling> consid. 1.2 p. 395).
2. Le litige porte sur le point de savoir si le recourant était fondé à suspendre le droit de l'intimé aux indemnités journalières de chômage. Le jugement entrepris présente les dispositions légales relatives à la suspension du droit aux indemnités journalières 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.
3. 3.1 La juridiction cantonale a considéré que l'intimé avait établi avec suffisamment de vraisemblance qu'il avait envoyé à l'ORP la liste de ses recherches d'emploi pour le mois de mars, le 7 avril 2006. Certes, il n'avait pas envoyé cette liste de recherches d'emploi par lettre-signature. Il convenait cependant de prendre en considération le fait qu'il ne pouvait pas se permettre d'ignorer le rappel du 6 avril 2006 de l'ORP, compte tenu de sa situation financière précaire; par ailleurs, sa note par laquelle il demandait un soutien par sa conseillère en placement, pour ses démarches auprès de l'Office cantonal de l'assurance-invalidité, démontrait qu'il était important, pour lui, que son envoi parvienne l'ORP en temps utile. Enfin, le fait qu'il envoyait désormais tous ses courriers par lettre-signature, pour éviter toute nouvelle sanction, constituait un indice supplémentaire de sa bonne foi et permettait d'accréditer ses allégations.
3.2 Le faisceau d'indices sur lequel s'est fondée la juridiction cantonale ne suffit pas à démontrer que l'intimé a bien remis en temps utile la liste de ses recherches d'emploi. Ses allégations sont, certes, plausibles, mais ne sont étayées par aucune preuve. Sa demande relative à une candidature pour un poste auprès de l'Office cantonal de l'assurance-invalidité suggère simplement à sa conseillère en placement qu'elle devrait effectuer certaines démarches après un entretien à l'ORP le 15 mai 2006; on ne peut rien en déduire quant à la date d'envoi du formulaire de recherches d'emploi pour le mois de mars. Par ailleurs, le seul intérêt financier de l'intimé à respecter le délai fixé par l'ORP pour éviter une mesure de suspension ne suffit pas à écarter une négligence de sa part, pas plus que le fait qu'il envoie désormais ses courriers par lettre-signature. A cet égard, on relèvera que le délai ordinaire pour déposer la liste de ses recherches d'emploi en mars 2006 était déjà échu lorsque l'ORP lui a envoyé un rappel; par ailleurs, la lettre de rappel du 6 avril 2006 l'informait du risque de suspension du droit à l'indemnité qu'il encourait en cas de non-respect du nouveau délai qui lui était imparti pour effectuer la démarche requise. Dans ces conditions, il était raisonnablement exigible, après ce rappel et l'avertissement relatif aux conséquences d'un retard, qu'il s'assure de pouvoir prouver l'envoi de la liste de ses recherches d'emploi en temps utile, ou du moins qu'il s'assure que cet envoi était bien parvenu à son destinaire.
3.3 Vu ce qui précède, les premiers juges ne pouvaient tenir pour établi, en se fondant sur les seules allégations de l'intimé, qu'il avait envoyé en temps utile la liste de ses recherches d'emploi pour le mois de mars 2006. Il convient par conséquent d'annuler le jugement entrepris et de confirmer la mesure de suspension prononcée par le recourant.
4. La procédure porte sur l'octroi ou le refus de prestations d'assurance, de sorte qu'elle est gratuite (art. 134 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et la décision du Tribunal des assurances sociales de la République et Canton de Genève du 7 novembre 2006 est annulée.
2. Il n'est pas perçu de frais judiciaires.
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 3 janvier 2008
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral