Faits: A. Le 2 septembre 2011, C._ s'est inscrite au chômage et un délai-cadre d'indemnisation de deux ans lui a été ouvert à partir de cette date. Par décision du 15 décembre 2011, l'Office régional de placement de X._ (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 novembre 2011 dans le délai légal, soit le 5 décembre 2011 au plus tard. Après avoir pris contact avec l'ORP et lui avoir fait parvenir une copie des documents requis le 21 décembre suivant, l'assurée a formé opposition à la décision de suspension, en faisant valoir qu'elle avait déposé, comme à son habitude, ses recherches d'emploi dans la boîte aux lettres de l'ORP le 3 décembre 2011. 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 13 mars 2012. B. L'assurée a recouru contre cette dernière décision devant la Cour des assurances sociales du Tribunal cantonal vaudois. Dans son écriture, elle a mentionné que son mari pouvait confirmer ses dires, mais qu'elle supposait que la valeur de ce témoignage allait être relativisée en raison du lien conjugal les unissant. Le tribunal cantonal a recueilli le témoignage du mari de l'assurée. Selon les déclarations de celui-ci, le samedi 3 décembre 2011, toute la famille était allée faire des courses ensemble et s'était ensuite rendue au bâtiment de l'ORP où C._ avait déposé l'enveloppe contenant ses recherches d'emploi dans la boîte aux lettres prévue à cet effet. L'époux de l'assurée s'en souvenait bien car la leçon de hockey de son fils avait été annulée ce samedi matin-là. Statuant le 25 juin 2012, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 13 mars 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. C._ conclut au rejet du recours. Le Secrétariat d'Etat à l'économie a renoncé à se déterminer. 