Faits :
A.
A._ travaillait depuis le 12 mai 2014 au service de la société B._ en qualité de femme de ménage. Le 19 juin 2014, alors qu'elle était en temps d'essai, elle a résilié les rapports de travail avec effet au 22 juin 2014.
La prénommée s'est inscrite auprès de l'Office régional de placement de Genève et a requis l'octroi d'indemnités de chômage dès le 25 septembre 2014.
Par décision du 23 décembre 2014, Syna Caisse de chômage (ci-après: la caisse) a suspendu le droit de l'assurée à l'indemnité de chômage durant 37 jours à partir du 25 septembre 2014, pour chômage fautif. Cette décision n'a pas été contestée.
Par décision du 12 mars 2015, l'Office cantonal de l'emploi (ci-après: l'OCE) a sanctionné l'assurée pour recherches d'emploi "nulles" pendant les trois mois ayant précédé son inscription au chômage et prononcé une suspension supplémentaire du droit à l'indemnité de chômage durant 12 jours à partir du 25 septembre 2014. Le 9 avril 2015, A._ s'est opposée à cette décision.
Par une nouvelle décision du 26 juin 2015, l'OCE a partiellement admis l'opposition et a ramené la durée de la suspension du droit à l'indemnité à 9 jours. L'assurée avait démontré avoir effectué quatre recherches d'emploi durant les trois mois ayant précédé son inscription au chômage, de sorte qu'il y avait lieu de lui appliquer le barème en cas de recherches insuffisantes et non de recherches "nulles" durant ladite période.
B.
A._ a recouru contre cette décision sur opposition devant la Chambre des assurances sociales de la Cour de justice de la République et canton de Genève, en demandant l'annulation de la sanction.
Statuant le 14 octobre 2015, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 26 juin 2015.
C.
L'OCE interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation.
A._ conclut au rejet du recours, tandis que le Secrétariat d'Etat à l'économie (SECO) ne s'est pas déterminé.

Considérant en droit :
1.
Le recours est dirigé contre un arrêt final (<ref-law>) rendu en matière de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi. Il est donc recevable.
2.
Le litige porte sur la suspension du droit de l'assurée à l'indemnité de chômage pendant 9 jours prononcée par décision sur opposition du 26 juin 2015, pour recherches d'emploi insuffisantes avant le début du chômage.
3.
3.1. Selon l'art. 30 al. 1 let. c LACI (RS 837.0), le droit de l'assuré à l'indemnité est suspendu lorsqu'il est établi que celui-ci ne fait pas tout ce qu'on peut raisonnablement exiger de lui pour trouver un travail convenable. Cette disposition doit être mise en relation avec l'<ref-law>, aux termes duquel l'assuré qui fait valoir des prestations d'assurance doit, avec l'assistance de l'office du travail compétent, entreprendre tout ce qu'on peut raisonnablement exiger de lui pour éviter le chômage ou l'abréger; il lui incombe, en particulier, de chercher du travail, au besoin en dehors de la profession qu'il exerçait précédemment ainsi que d'apporter la preuve des efforts fournis.
3.2. La durée de la suspension dans l'exercice du droit à l'indemnité est de 1 à 15 jours en cas de faute légère, 16 à 30 jours en cas de faute de gravité moyenne et 31 à 60 jours en cas de faute grave (<ref-law>).
4.
4.1. Les premiers juges ont retenu que les conditions d'application de l'art. 30 al. 1 let. c LACI n'étaient pas données en l'espèce. Constatant que l'assurée avait donné son congé pendant le temps d'essai (en juin 2014) et qu'elle s'était inscrite au chômage le 25 septembre 2014, ils ont considéré que l'OCE aurait dû examiner ses efforts en vue de trouver un emploi durant le seul délai de congé de trois jours, et non pas durant les trois mois ayant précédé son inscription au chômage. Rappelant par ailleurs que l'<ref-law> avait pour but de sanctionner la sollicitation abusive des prestations et de mettre une partie du dommage à la charge de l'assuré en cas de chômage fautif, la juridiction cantonale a considéré que l'intimée avait suffisamment contribué à diminuer le dommage à l'assurance en retardant son inscription au chômage de trois mois après la perte de son emploi.
4.2. Comme le relève à bon droit le recourant, l'obligation de rechercher un emploi prend déjà naissance avant la survenance effective du chômage. Il incombe, en particulier, à un assuré de s'efforcer déjà pendant le délai de congé de trouver un nouvel emploi et, de manière générale, durant toute la période qui précède l'inscription au chômage. Les efforts de recherches d'emploi doivent en outre s'intensifier à mesure que le chômage devient imminent (<ref-ruling> consid. 2.1.2 p. 526; arrêts 8C_800/2008 du 8 avril 2009 consid. 2.1, C 208/03 du 26 mars 2004 consid. 3.1, in DTA 2005 n° 4 p. 56; BORIS RUBIN, Commentaire de la loi sur l'assurance-chômage, 2014, n° 9 s. ad <ref-law>, p. 198 s., THOMAS NUSSBAUMER, Arbeitslosenversicherung, in Soziale Sicherheit, SBVR vol. XIV, 3ème éd. 2016, n° 843 p. 2517).
L'obligation de rechercher un emploi vaut même si l'assuré retarde son inscription au chômage. Selon la jurisprudence en effet, le fait de retarder son inscription au chômage après une résiliation des rapports de travail n'est propre à réduire le dommage causé à l'assurance que si l'assuré s'est efforcé, aussi bien durant le délai de résiliation du contrat de travail que pendant la période située entre la fin des rapports de travail et le début du délai-cadre d'indemnisation, de rechercher un emploi avec toute l'intensité requise (cf. arrêts 8C_761/2009 du 23 décembre 2009 consid. 3.5 et la référence citée et C 73/03 du 28 décembre 2005 consid. 3.3).
4.3. En l'occurrence, l'intimée a donné son congé le 19 juin 2014 pour le 22 juin suivant. Elle ne s'est inscrite à l'assurance chômage que le 25 septembre 2014, soit plus de trois mois après la fin de ses rapports de travail. Au cours de cette période, elle a apporté la preuve de seulement quatre recherches d'emploi au cours des mois de juin et de juillet 2014, ce qui est manifestement insuffisant au regard de l'art. 30 al. 1 let. c LACI (<ref-ruling> consid. 2.1.4 p. 528). La sanction prononcée à l'encontre de l'intimée doit dès lors être confirmée. La durée de celle-ci ne prête pas le flanc à la critique et l'intimée ne la conteste au demeurant pas.
5.
5.1. Par une double motivation, les premiers juges ont retenu que l'exécution de la suspension du droit à l'indemnité était en tout état de cause caduque. En effet, dès lors que le délai de congé avait pris fin le 22 juin 2014, le délai de suspension de six mois avait commencé à courir le 1 er jour après la fin du contrat de travail de l'assurée, à savoir le 23 juin 2014. Partant, au moment de la décision de suspension du 26 janvier 2015 (recte: 12 mars 2015), le délai de six mois avait déjà expiré.
5.2. Le recourant soutient au contraire que la suspension n'était pas caduque. Selon lui, le délai de suspension avait commencé à courir le 1 er jour de l'ouverture du délai-cadre d'indemnisation de l'intimée, soit le 25 septembre 2015, de sorte qu'en prononçant la suspension du droit à l'indemnité de chômage le 12 mars 2015, le recourant avait agi en temps utile.
5.3.
5.3.1. L'exécution de la suspension est caduque six mois après le début du délai de suspension (art. 30 al. 3, 4ème phrase, LACI). Aux termes de l'<ref-law>, le délai de suspension dans l'exercice du droit à l'indemnité prend effet à partir du premier jour qui suit la cessation du rapport de travail lorsque l'assuré est devenu chômeur par sa propre faute (let. a) ou à partir du premier jour qui suit l'acte ou la négligence qui fait l'objet de la décision (let. b).
5.3.2. En ce qui concerne le motif de suspension prévu à l'art. 30 al. 1 let. c LACI, l'<ref-law> doit être compris en ce sens que la suspension dans l'exercice du droit à l'indemnité prend effet à partir du premier jour qui suit la cessation du rapport de travail lorsque l'assuré ne s'est pas suffisamment efforcé de trouver un travail convenable avant la fin du contrat de travail. Si, en revanche, les manquements reprochés à l'assuré se sont poursuivis après ce moment-là, le début du délai d'exécution de la suspension est défini par l'<ref-law> (avant le 1 er avril 2011, let. c). Tel est en particulier le cas lorsque l'assuré ne s'inscrit pas immédiatement au chômage après la perte de son emploi et qu'il n'effectue pas suffisamment de recherches d'emploi avant son inscription au chômage. On applique ici le principe qui veut que lorsqu'un assuré adopte un comportement continuellement contraire à ses devoirs, le délai de suspension ne commence à courir que le jour suivant le dernier acte ou omission passible d'une sanction (arrêt 8C_642/2007 du 4 août 2008, in DTA 2009 172, consid. 4.4.1 p. 176; BORIS RUBIN, op. cit., n° 134 ad <ref-law>, p. 333).
5.3.3. En l'occurrence, les manquements reprochés à l'intimée se rapportent à la période située entre le 22 juin et le 25 septembre 2014. En vertu de l'<ref-law>, le délai d'exécution de la suspension a donc commencé à courir au plus tôt le 26 septembre 2014. Par conséquent, l'OCE a agi en temps utile en prononçant la suspension du droit à l'indemnité de chômage le 12 mars 2015.
6.
Il résulte de ce qui précède que le recours est bien fondé.
7.
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. La décision de la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, du 14 octobre 2015 est annulée et la décision sur opposition de l'Office cantonal de l'emploi du 26 juin 2015 confirmée.
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, à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, et au Secrétariat d'Etat à l'économie (SECO).
Lucerne, le 15 juillet 2016
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Juge présidant : Ursprung
La Greffière : Fretz Perrin