Faits: A. Le 18 janvier 2010, Q._ s'est inscrite au chômage et un délai-cadre d'indemnisation de deux ans lui a été ouvert à partir du 1 er février 2010. Par décision du 18 octobre 2011, l'Office régional de placement de la Riviera (ORP) a prononcé une suspension du droit à l'indemnité de l'assurée pour une durée de 5 jours, au motif qu'elle n'avait pas remis ses recherches d'emploi du mois de septembre 2011 dans le délai légal, soit le 5 octobre 2011 au plus tard. L'assurée a formé opposition à la décision de suspension. Elle a indiqué qu'elle avait demandé à sa mère de déposer ses recherches d'emploi dans la boîte aux lettres de l'ORP le 4 octobre 2011, compte tenu du fait que les bureaux étaient déjà fermés. Le même jour, sa mère avait également déposé la feuille IPA (indications de la personne assurée) de l'assurée à la caisse de chômage située dans le même immeuble que l'ORP. Ce n'est que le 13 octobre suivant, lors d'un entretien avec sa conseillère ORP que l'assurée avait appris, à son grand étonnement, que ses recherches d'emploi n'étaient jamais parvenues à l'ORP alors que sa feuille IPA avait bien été réceptionnée. Le Service de l'emploi du canton de Vaud (ci-après: le service de l'emploi) a écarté l'opposition dans une nouvelle décision du 9 février 2012. B. L'assurée a recouru contre cette dernière décision devant la Cour des assurances sociales du Tribunal cantonal du canton de Vaud. Le tribunal cantonal a recueilli le témoignage de la mère de l'assurée. Selon les déclarations de celle-ci, comme elle l'avait déjà fait à plusieurs reprises pour sa fille, elle était allée apporter deux enveloppes, l'une à l'ORP et l'autre à la caisse de chômage. Ces deux institutions étaient logées dans le même immeuble au troisième étage. La mère de l'assurée a indiqué avoir mis les enveloppes dans les boîtes aux lettres respectives se trouvant à l'étage. Statuant le 28 mai 2013, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 9 février 2012 ainsi que la sanction litigieuse. C. Le service de l'emploi interjette un recours en matière de droit public contre ce jugement, en concluant à son annulation et à la confirmation de sa décision sur opposition. Q._ conclut au rejet du recours, tandis que le Secrétariat d'Etat à l'économie a renoncé à se déterminer.