Faits: A. X._, né en 2007, et Y._, née en 2009, sont les enfants, nés hors mariage, de B._ (mère) et de A._ (père). Le 3 juillet 2010, les parents se sont séparés et rencontrent d'importantes difficultés de communication et de collaboration. B. Le 21 juillet 2010, le père a saisi le Tribunal tutélaire d'une demande de fixation des relations personnelles avec les enfants. Après avoir pris connaissance du rapport d'évaluation du 22 septembre 2010 du Service de protection des mineurs (ci-après: SPMi) et entendu les parents lors d'une audience le 14 octobre 2010 au cours de laquelle le père a indiqué souhaiter à terme une garde alternée, le Tribunal tutélaire a, par décision du 15 octobre 2010, notamment fixé les relations personnelles du père avec ses enfants à raison d'un mercredi sur deux, la fille rentrant chez elle à midi, et tous les samedis de 8h30 à 17h00. Le 4 avril 2011, à la suite du rapport du SPMi du 4 février 2011 et de l'audition des parents du 24 mars 2011, le Tribunal tutélaire a modifié la réglementation du droit de visite, le père ayant ses enfants un mercredi sur deux de 8h30 à 17h00 et un week-end sur deux, pour X._ du samedi 8h30 au dimanche 17h00, pour Y._ sans les nuits, à savoir les samedis et dimanches de 8h30 à 17h00. B.a Statuant le 9 février 2012 sur le rapport d'évaluation du 7 octobre 2011 du SPMI proposant l'élargissement du droit de visite, le Tribunal tutélaire, après avoir entendu les parents et la représentante du SPMi à l'audience du 8 décembre 2011, a fixé les relations personnelles du père avec ses enfants à raison d'un mercredi sur deux de 8h30 à 17h00, d'un week-end sur deux du samedi 8h30 au dimanche 17h00 et durant la moitié des vacances scolaires. Le père a formé appel contre ce jugement le 27 février 2012, concluant à l'octroi, principalement de la garde alternée à raison d'une semaine sur deux, subsidiairement d'un droit de visite s'exerçant toutes les semaines du mardi à la sortie de l'école/la crèche au jeudi matin, un week-end sur deux du vendredi soir au lundi matin et durant la moitié des vacances scolaires. La mère a déposé une réponse le 27 février [recte: le 28 mars] 2012, demandant la confirmation de la décision du Tribunal tutélaire. Par courrier du 23 avril 2012, le père a sollicité un deuxième échange d'écritures ou, à tout le moins, une audience de plaidoirie. B.b Par arrêt du 25 avril 2012, la Chambre de surveillance du Tribunal tutélaire de la Cour de justice du canton de Genève (ci-après: la Chambre de surveillance) a rejeté l'appel. C. Par acte du 28 mai 2012, le père interjette un recours en matière civile au Tribunal fédéral. Il conclut à l'annulation de l'arrêt entrepris et principalement à sa réforme en ce sens que son droit de visite s'exerce un mercredi sur deux de 8h30 à 18h00, un week-end sur deux du vendredi 18h00 au dimanche 18h00 et la moitié des vacances scolaires, subsidiairement à son renvoi devant l'autorité précédente. Invitée à se déterminer, l'intimée s'en rapporte à justice quant à la recevabilité du recours et conclut au fond au rejet du recours. L'autorité précédente expose ne pas avoir d'observations à formuler et se réfère aux considérants de son arrêt.