Faits:
A. Sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'Office des poursuites de Genève (ci-après: l'office) a fait notifier, le 9 septembre 2011, à X._ SA un commandement de payer (poursuite no 00 000000 U) trois montants distincts de 75'000 fr., avec intérêts à 5% respectivement dès les 31 décembre 2006, 2007 et 2008. Ce commandement de payer indiquait sous la rubrique titre et date de la créance, cause de l'obligation: " 1) Atteinte au crédit, 2) Fausse facturation avec inscription fallacieuse et illicite par l'administrateur de Z._ SA, M. Y._, administrateur de X._ SA, 3) Abus de confiance ". La débitrice y a fait opposition.
Egalement sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'office a fait notifier, le 9 septembre suivant, à X._ SA un deuxième commandement de payer (poursuite no 00 000000 T) la somme de 321'015 fr. 85, plus intérêts à 5% dès le 20 février 2010. L'acte de poursuite mentionnait sous la rubrique titre et date de la créance, cause de l'obligation: " 1) Remboursement sur facturation indue, facturation illicite et abus du mandat d'administrateur de Z._ SA, 2) Atteinte au crédit ". La débitrice y a fait opposition.
Toujours sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'office a fait notifier, le 12 septembre 2011, à Y._, un commandement de payer (poursuite no 00 000000 W) portant sur 42'000 fr., avec intérêts à 5% dès le 1er janvier 1998, 18'000 fr. avec intérêts à 5% dès le 1er janvier 2009 et 24'862 fr. 45, avec intérêts à 5% dès le 1er janvier 2010. La rubrique titre et date de la créance, cause de l'obligation indiquait: " 1) Rbt avance à Y._ pour travaux xxx (1997), 2) Rbt avance à Y._ pour travaux villa yyy, 3) Rbt avance à Y._ pour indemnité zzz selon décision du tribunal ". Il y a été fait opposition.
Enfin, toujours sur réquisition du 10 août 2011 du même créancier, l'office a fait notifier, le 15 septembre 2011, derechef à Y._ un dernier commandement de payer (poursuite no 00 000000 V) le montant de 1'546'000 fr., sans intérêt. Sous la rubrique titre et date de la créance, cause de l'obligation figuraient comme indications: " 1) Prélèvement indu avec abus de la signature sociale de la société, 2) enrichissement illégitime et concurrence déloyale en tant qu'administrateur de la SA, 3) Atteinte au crédit ". Il y a aussi été fait opposition.
B. B.a Le 19 septembre 2011, Y._ et X._ SA ont formé plainte contre les notifications, les 9 et 12 septembre 2011, des trois premiers commandements de payer susmentionnés devant la Chambre de surveillance de l'office, motifs pris que ces poursuites, fondées sur des créances contestées ou inexistantes, étaient constitutives d'un abus de droit et n'avaient aucun autre but que celui de les tourmenter délibérément. Ils ont soutenu en particulier qu'elles faisaient en effet suite à des poursuites qu'ils avaient eux-mêmes notifiées à A._, administrateur de Z._ SA, en paiement de dépens auxquels celui-ci avait été condamné. Elles s'inscrivaient ainsi dans un contexte de représailles ayant pour seul but de leur nuire dans le cadre de leur activité de promotion immobilière. Les plaignants ont requis l'apport en procédure d'un extrait des poursuites pendantes à l'encontre de Z._ SA.
Le 26 septembre 2011, Y._ et X._ SA ont déposé une seconde plainte dirigée cette fois contre la notification, le 15 septembre 2011, du dernier commandement de payer. Ils ont invoqué les mêmes motifs que dans leur précédente plainte.
B.b Dans ses observations des 22 septembre et 3 octobre 2011, l'office a conclu au rejet de ces plaintes, motifs pris que l'abus de droit allégué n'était pas manifeste et qu'il n'appartenait par ailleurs pas aux autorités de poursuite de revoir la justification des créances à l'origine de la procédure de réalisation forcée.
Le 17 octobre 2011, Z._ SA a aussi proposé le rejet des plaintes et déposé diverses pièces.
Y._ et X._ SA ont répliqué par écriture du 30 novembre 2011, reçue par le greffe le 1er décembre suivant. Ils ont par ailleurs produit un jugement du Tribunal de première instance du 13 octobre 2011 attribuant à X._ SA le 50% du capital actions de Z._ SA.
Sur interpellation de la Chambre de surveillance des offices des poursuites et faillites, l'office a fait parvenir à cette autorité, le 27 février 2012, les copies des réquisitions de poursuite susmentionnées introduites par A._ pour le compte de Z._ SA à l'encontre de X._ SA et Y._, ainsi que l'extrait informatique du Registre du commerce concernant Z._ SA, imprimé le 24 février 2012. Dans la lettre du 24 février 2012 accompagnant cet envoi, il s'est déterminé sur un argument de la réplique des plaignants qui se fondait sur le jugement du 13 octobre 2011 attribuant à X._ SA le 50% du capital actions de Z._ SA. Il s'est référé, pour le surplus, à ses précédentes observations.
Par courrier du 13 mars 2012 reçu le lendemain, Z._ SA a pris position sur cette détermination et a versé diverses pièces au dossier.
Le 16 avril 2012, Y._ et X._ SA ont déposé de nouvelles observations en relation notamment avec le rapport complémentaire de l'office du 24 février précédent.
B.c Par décision du 14 juin 2012, la Cour de justice du canton de Genève, statuant en sa qualité de Chambre de surveillance des Offices des poursuites et faillites, a préalablement ordonné la jonction des causes et l'apport au dossier de l'extrait des poursuites à l'encontre de Z._ SA. Au fond, elle a rejeté les plaintes.
C. Par écriture du 29 juin 2012, Y._ et X._ SA exercent un recours en matière civile au Tribunal fédéral. Ils concluent principalement à l'annulation de la décision cantonale et à sa réforme en ce sens que les poursuites litigieuses sont annulées. Ils demandent subsidiairement que le dossier soit retourné à l'autorité cantonale pour nouvelle décision au sens des considérants.
Z._ SA propose le rejet du recours. Ni la Chambre de surveillance ni l'office ne se sont déterminés.

Considérant en droit:
1. Le recours a été formé en temps utile (<ref-law>) contre une décision finale (<ref-law>; <ref-ruling> consid. 1.2) rendue en matière de poursuite pour dettes (<ref-law>) par une autorité de surveillance ayant statué en dernière (unique) instance cantonale (<ref-law>; MARCO LEVANTE, in: Basler Kommentar, SchKG I, 2ème éd., 2010, n° 19 ad <ref-law>); il est ouvert indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF); les plaignants, dont les conclusions ont été rejetées sur le fond par la juridiction précédente, ont qualité pour recourir (<ref-law>).
2. Les recourants se plaignent d'abord d'une violation de leur droit d'être entendus, plus précisément de leur droit à une réplique garanti par les art. 29 al. 2 Cst. et 6 CEDH. Ils reprochent à la Chambre de surveillance de les avoir privés de leur droit à se déterminer sur l'extrait des poursuites pendantes à l'encontre de la société intimée en n'ordonnant l'apport au dossier de cette pièce que dans la décision attaquée, préalablement, au fond. Ils lui font aussi grief de ne pas leur avoir transmis les observations de cette société reçue au greffe le 14 mars 2012.
2.1 Le droit d'être entendu est une garantie constitutionnelle de nature formelle, dont la violation entraîne l'annulation de la décision attaquée sans égard aux chances de succès du recours sur le fond (<ref-ruling> consid. 3d/aa p. 437). Ce moyen doit par conséquent être examiné en premier lieu (<ref-ruling> consid. 1 p. 50) et avec un plein pouvoir d'examen (<ref-ruling> consid. 3 p. 194 et la jurisprudence citée).
Compris comme l'un des aspects de la notion générale de procès équitable au sens des art. 29 Cst. et 6 CEDH, le droit d'être entendu garantit notamment le droit pour une partie à un procès de prendre connaissance de toute argumentation présentée au tribunal et de se déterminer à son propos, 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. Il appartient en effet 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. 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 (<ref-ruling> consid. 4.5 p. 103 s; <ref-ruling> consid. 3.1 p. 277; <ref-ruling> consid. 2.2. p. 190; arrêt 1C_196/2011 du 11 juillet 2011 consid. 2.2 publié in SJ 2012 I p. 117; arrêt 5A_779/2010 du 1er avril 2011 consid. 2.2 publié à la FamPra.ch 2012 no 1 p. 1).
2.2 En l'espèce, dans leurs plaintes, les recourants ont requis l'apport à la procédure de l'extrait des poursuites pendantes à l'encontre de l'intimée, document dont ils prétendaient qu'il permettrait d'établir que cette dernière les poursuit en représailles à leurs propres poursuites. Certes, ainsi que le soutient l'intimée, en ordonnant l'apport de cette pièce dans sa décision du 14 juin 2012 - préalablement au fond -, la Chambre de surveillance s'est bornée à faire droit à cette requête. Elle a toutefois omis de communiquer ce moyen de preuve aux recourants, qui n'ont ainsi pas pu se déterminer sur son contenu, en particulier sur sa portée quant au fait allégué dans leurs plaintes. De même, elle ne leur a pas transmis la détermination du 13 mars 2012 sur les observations de l'office du 24 février 2012 que la société intimée a déposée au greffe le 14 mars 2012. Contrairement à ce que plaide cette dernière, que cette écriture 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 n'est pas relevant selon la jurisprudence du Tribunal fédéral (cf. supra, consid. 2.1). Cela étant, c'est à bon droit que les recourants reprochent à l'autorité cantonale d'avoir violé leur droit à la réplique.
Le recours devant être admis pour ce motif tiré de la violation d'une garantie constitutionnelle de nature formelle, il n'est pas nécessaire d'examiner les autres griefs soulevés par les recourants.
3. Vu ce qui précède, la décision attaquée doit par conséquent être annulée et la cause renvoyée à l'autorité cantonale pour nouvelle décision prise dans le respect du droit à la réplique défini ci-dessus. Quoiqu'elle n'ait pas occasionné la décision déférée, l'intimée s'est opposée au recours sur la question de la violation du droit d'être entendu. Elle doit dès lors être considérée comme la partie qui succombe et supporter ainsi les frais et dépens de la procédure (art. 66 al. 1 et 68 al. 1, 2 et 4 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. La décision attaquée est annulée. La cause est renvoyée à l'autorité cantonale pour nouvelle décision dans le sens des considérants.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de l'intimée.
3. L'intimée versera aux recourants, solidairement entre eux, la somme de 3'000 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, à l'Office des poursuites de Genève et à la Cour de justice du canton de Genève, Chambre de surveillance des Offices des poursuites et faillites.
Lausanne, le 10 septembre 2012
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Juge présidant: Escher
La Greffière: Jordan