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.

Considérant en droit:
1. L'arrêt entrepris, qui a pour objet la réglementation du droit de visite du parent non marié qui n'a pas la garde des enfants, est une décision prise en application de normes de droit public dans une matière connexe au droit civil (art. 72 al. 2 let. b ch. 7 LTF; arrêts 5A_763/2011 du 7 mars 2012 consid. 1; 5A_457/2009 du 9 décembre 2009 consid. 1.1). Comme la question soumise au Tribunal fédéral est de nature non pécuniaire, le recours est ouvert indépendamment de la valeur litigieuse (arrêts 5A_366/2010 du 4 janvier 2011 consid. 1.1, 5D_41/2007 du 27 novembre 2007 consid. 2.3). Par ailleurs, le recours a été interjeté dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, par une partie ayant pris part à la procédure devant l'autorité précédente et justifiant d'un intérêt digne de protection à la modification ou à l'annulation de la décision attaquée (<ref-law>), contre une décision finale (<ref-law>), rendue sur recours par une autorité supérieure statuant en dernière instance cantonale (art. 75 al.1 et 2 LTF). Le recours en matière civile est donc en principe recevable.
2. Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Compte tenu des exigences de motivation posées, sous peine d'irrecevabilité (<ref-law>), à l'<ref-law>, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 1.4 p. 400; <ref-ruling> consid. 1.1 p. 104 s.). En outre, le Tribunal fédéral ne connaît de la violation des droits fondamentaux que si un tel grief a été soulevé et motivé par le recourant (<ref-ruling> consid. 3.3 p. 310 s.; <ref-ruling> consid. 1.4.2 p. 254). Le recourant qui se plaint de la violation de droits fondamentaux doit ainsi satisfaire au principe d'allégation, en indiquant précisément quelle disposition constitutionnelle a été violée et en démontrant, par une argumentation précise, en quoi consiste la violation (<ref-law>; <ref-ruling> consid. 1.4 p. 287; <ref-ruling> consid. 1.4.2 p. 254). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 3.1 p. 399 in fine).
3. Le présent recours a pour objet les modalités d'exercice du droit de visite du parent non gardien sur ses deux enfants nés hors mariage; le recourant reproche aux juges cantonaux d'avoir violé, d'une part, son droit d'être entendu (art. 29 al. 2 Cst.) et, d'autre part, l'<ref-law>.
4. Invoquant son droit d'être entendu garanti par l'art. 29 al. 2 Cst., le recourant fait valoir que la cour cantonale devait ordonner un deuxième échange d'écritures ainsi qu'il le souhaitait ou, à tout le moins fixer une audience de plaidoiries, afin qu'il puisse "réagir aux observations de B._ du 28 mars 2012 et qui lui ont été transmises par l'autorité cantonale par pli du 11 avril 2012".
4.1 Le droit d'être entendu est un grief de nature formelle (<ref-ruling> consid. 3d/aa p. 437 s.), dont la violation entraîne l'annulation de la décision attaquée indépendamment des chances de succès du recours sur le fond (<ref-ruling> consid. 3d/aa p. 437), qu'il convient par conséquent d'examiner avant tout autre (<ref-ruling> consid. 2.6.1 p. 285; <ref-ruling> consid. 1 p. 50) et avec une cognition libre (<ref-ruling> consid. 2a p. 57 et les arrêts cités).
4.1.1 Compris comme l'un des aspects de la notion générale de procès équitable au sens des art. 29 Cst., le droit d'être entendu garantit notamment au justiciable le droit de s'expliquer avant qu'une décision ne soit prise à son détriment, d'avoir accès au dossier, de prendre connaissance de toute argumentation présentée au tribunal et de se déterminer à son propos, dans la mesure où il l'estime nécessaire, que celle-ci contienne ou non de nouveaux éléments de fait ou de droit, et qu'elle soit ou non concrètement susceptible d'influer sur le jugement à rendre (<ref-ruling> consid. 2.3.3 p. 157; <ref-ruling> consid. 2.3.1 p. 197; <ref-ruling> consid. 5.1 p. 293; <ref-ruling> consid. 4.3 p. 102; <ref-ruling> consid. 3.3.2 p. 46). Il appartient aux parties, et non au juge, de décider si une prise de position ou une pièce nouvellement versée au dossier contient des éléments déterminants qui appellent des observations de leur part. Ce droit à la réplique vaut pour toutes les procédures judiciaires (<ref-ruling> consid. 2. 5 p. 157; <ref-ruling> consid. 4.3 ss p. 102 ss, 98 consid. 2.2 p. 99; <ref-ruling> consid. 3.3.2 - 3.3.4 p. 46 s.). Toute prise de position ou pièce nouvelle versée au dossier doit dès lors être communiquée aux parties pour leur permettre de décider si elles veulent ou non faire usage de leur faculté de se déterminer (ATF <ref-ruling> consid. 2.3.1 p. 197; <ref-ruling> consid. 2.2 p. 99, 100 consid. 4.5 p. 103 s.; <ref-ruling> consid. 3.3.2 - 3.3.4 p. 46 s.; arrêt 5A_503/2010 du 28 mars 2011 consid. 2.2; cf. en outre les arrêts de la Cour européenne des droits de l'homme dans les causes Schaller-Bossert contre Suisse du 28 octobre 2010 § 39 s. et Nideröst-Huber contre Suisse du 18 février 1997, Recueil CourEDH 1997-I p. 101 § 24).
4.1.2 Les art. 322 et 327 du Code de procédure civile fédérale du 19 décembre 2008 (ci-après: CPC), applicables par le renvoi de l'art. 29 al. 1 de la loi genevoise du 28 novembre 2010 d'application du code civil suisse et autres lois fédérales en matière civile (entrée en vigueur le 1er janvier 2011, ci-après: LaCC), ne prévoient en principe qu'un seul échange d'écritures et une procédure sur pièces dans le cadre d'un recours contre une décision prise en matière de relations personnelles.
4.2 En l'occurrence, l'autorité cantonale a communiqué le mémoire de réponse de l'intimée du 28 mars 2012 [et non du 27 février 2012, comme l'indique l'arrêt attaqué de manière manifestement erronée, <ref-law>] au recourant par pli du 11 avril 2012. Il ressort par ailleurs des constatations de l'arrêt entrepris que le recourant a requis, par courrier du 23 avril 2012, un deuxième échange d'écritures ou, à tout le moins, une audience de plaidoirie. Il s'ensuit que le recourant a clairement exprimé sa volonté de s'exprimer sur la réponse de l'intimée, dans un délai raisonnable, et ne saurait ainsi être considéré comme s'étant abstenu.
L'autorité précédente a rejeté la requête du recourant, partant elle a refusé tout nouvel échange d'écritures et de tenir audience, directement dans son arrêt au fond rendu deux jours plus tard, le 25 avril 2012, exposant que les mesures requises "ne sont pas justifiées". L'autorité précédente - même si elle a la possibilité, dans un premier temps, de communiquer les écritures à titre d'information sans ordonner un deuxième échange d'écritures - ne saurait priver ce dernier de son droit d'être entendu en jugeant la cause deux jours après l'envoi de la requête alors qu'elle avait connaissance du fait que le recourant souhaitait s'exprimer sur la cause avant que le jugement soit rendu. Le recourant a ainsi appris le rejet de sa requête uniquement dans l'arrêt au fond daté du surlendemain, en sorte qu'il n'a pas pu disposer du temps nécessaire pour déposer des observations spontanées sur la réponse, à la suite du rejet de sa demande de nouvel échange d'écritures, subsidiairement de tenir audience. La procédure suivie par la Chambre de surveillance de la Cour de justice a donc manifestement privé le recourant de la faculté d'exercer son droit constitutionnel de s'exprimer sur sa cause avant d'être jugé.
4.3 Le Tribunal de céans peut - exceptionnellement - réparer une violation du droit d'être entendu s'il dispose d'un libre pouvoir de cognition, autrement dit lorsque seules des questions de droit demeurent litigieuses (<ref-ruling> consid. 2.2 p. 204, arrêt 5A_503/2010 du 28 mars 2011 consid. 2.4), et qu'il n'en résulte aucun préjudice pour le justiciable (<ref-ruling> consid. 5.1.2 a contrario p. 177).
En l'occurrence, contrairement à ce que prétend l'intimée, la Cour de céans ne peut valablement réparer la violation du droit d'être entendu alléguée à juste titre par le recourant, celui-ci se plaignant de l'application du droit fédéral à l'aune de la situation de l'espèce, en particulier du bien de l'enfant et du rapport d'expertise. Le grief de violation du droit d'être entendu (art. 29 Cst.) doit donc être admis, ce qui scelle le sort du recours sans qu'il faille examiner l'autre grief soulevé par le recourant.
5. Vu ce qui précède, le recours doit être admis, la décision attaquée annulée et la cause renvoyée à l'autorité précédente pour nouvelle décision. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de l'intimée, qui a conclu au rejet du recours (<ref-law>). Une indemnité de 2'500 fr., à payer à titre de dépens au recourant, est mise à la charge de l'intimée (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, la décision attaquée est annulée et la cause est renvoyée à l'autorité précédente pour nouvelle décision.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de l'intimée.
3. L'intimée versera au recourant la somme de 2'500 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4. Le présent arrêt est communiqué aux parties et à la Chambre de surveillance du Tribunal tutélaire de la Cour de justice du canton de Genève.
Lausanne, le 14 septembre 2012
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
La Greffière: Carlin