Faits:
A. R._ a été engagée en qualité de psychologue par les Institutions Y._ à dater du 1er mars 1990. Ces dernières ont été par la suite intégrées aux Institutions X._. Avec effet au 1er mars 1993, R._ a été nommée fonctionnaire. Elle a été absente de son poste depuis le 26 octobre 2009 pour raison de santé, sous réserve d'une tentative de reprise entre le 8 et le 23 mars 2010. Un litige étant survenu entre l'employeur et la fonctionnaire au sujet du bien-fondé de cette absence de longue durée, le conseil d'administration de X._ a signifié à l'intéressée, par lettre du 22 octobre 2010, qu'il avait décidé de la licencier pour le 31 janvier 2011.
B. R._ a déféré cette décision au Tribunal administratif de la République et canton de Genève (aujourd'hui: Cour de justice de la République et canton de Genève, Chambre administrative). Au cours de la procédure cantonale, il est apparu que la prénommée avait été mise à la retraite anticipée avec effet au 1er février 2011. Par arrêt du 21 août 2012, la juridiction cantonale a partiellement admis le recours. Elle a constaté que la décision de X._ du 22 octobre 2010 violait le droit d'être entendue de l'intéressée et condamné l'employeur à verser à celle-ci une indemnité correspondant à vingt-quatre mois de son dernier traitement brut, sous déduction des rentes perçues entre le 1er février 2011 et le 31 janvier 2013.
C. X._ interjettent un recours en matière de droit public contre ce jugement dont ils demandent l'annulation associée, ou non, au renvoi de la cause à la juridiction cantonale pour nouvelle décision. A titre préalable, ils concluent à l'octroi de l'effet suspensif.
L'intimée conclut au rejet du recours en toutes ses conclusions.

Considérant en droit:
1. 1.1 Selon l'art. 83 let. g LTF, en matière de rapports de travail de droit public (lorsque, comme en l'espèce, la question de l'égalité des sexes n'est pas en cause), le recours en matière de droit public est irrecevable contre les décisions qui concernent une contestation non pécuniaire. Pour que le recours soit recevable, il faut encore, en principe, que la valeur litigieuse minimale de 15'000 fr. soit atteinte (<ref-law>).
1.2 En l'occurrence, le litige porte sur le versement d'une indemnité correspondant à vingt-quatre fois le dernier traitement mensuel brut de l'intimée (8'080 fr. 50), sous déduction du montant de la rente mensuelle de vieillesse (5'018 fr. 35) qu'elle aura perçue durant la période concernée, soit 73'491 fr. 60. Le seuil de la valeur litigieuse déterminante est donc largement dépassé.
2. 2.1 La loi cantonale genevoise relative au personnel de l'administration cantonale, du pouvoir judiciaire et des établissements publics médicaux du 4 décembre 1997 (LPAC; RS/GE B 5 05), applicable auprès de X._ (art. 1er, al. 1, let. e), prévoit à son art. 31 LPAC, que peut recourir à la Chambre administrative de la Cour de justice (antérieurement : le Tribunal administratif) pour violation de la loi tout membre du personnel dont les rapports de service ont été résiliés (al. 1). Si la Chambre administrative de la Cour de justice retient que la résiliation des rapports de service est contraire au droit, elle peut proposer à l'autorité compétente la réintégration (al. 2). En cas de décision négative de l'autorité compétente, la Chambre administrative de la Cour de justice fixe une indemnité dont le montant ne peut être inférieur à un mois et supérieur à vingt-quatre mois du dernier traitement brut à l'exclusion de tout autre élément de rémunération (al. 3, 1ère phrase).
2.2 Le jugement attaqué retient que l'intimée a été pratiquement obligée d'accepter une mise à la retraite anticipée et qu'il en est résulté pour elle un important préjudice financier. Les premiers juges ont estimé que son cas différait ainsi de celui du fonctionnaire licencié contrairement au droit et qui peut encore retrouver un emploi équivalent, l'indemnité de l'art. 31 al. 3 LPAC étant destinée à assurer son traitement pendant les mois au cours desquels il se trouve sans emploi. Ils ont considéré qu'il serait choquant que la situation de l'intimée se trouvât péjorée, alors que le licenciement dont elle a été victime après vingt ans de service s'était révélé contraire au droit (consid. 8).
2.3 Les recourants reprochent aux premiers juges d'avoir retenu, au regard des seules allégations de R._, que celle-ci avait été obligée d'accepter une mise à la retraite anticipée et de lui avoir par conséquent accordé une indemnité, alors que son recours eût dû être déclaré irrecevable selon le droit cantonal et la jurisprudence y relative de la Chambre administrative de la Cour de justice.
3. Le recours en matière de droit public devant le Tribunal fédéral ne peut pas être interjeté pour violation du droit cantonal en tant que tel, mais il est possible de faire valoir qu'une mauvaise application du droit cantonal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à d'autres droits constitutionnels (<ref-ruling> consid. 4.3 p. 521 s.; <ref-ruling> consid. 2.3 p. 466). Selon la jurisprudence, une décision est arbitraire au sens de l'art. 9 Cst. lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité (<ref-ruling> consid. 2.1 p. 211; <ref-ruling> consid. 2 p. 61). S'agissant de la manière dont le droit cantonal a été appliqué, il ne faut pas confondre arbitraire et violation de la loi: une violation doit être manifeste et reconnue d'emblée pour être considérée comme arbitraire. Le Tribunal fédéral n'a pas à examiner quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement dire si l'interprétation qui a été opérée est défendable. Il n'y a pas arbitraire du seul fait qu'une autre solution paraît également concevable, voire préférable (<ref-ruling> consid. 5.1 p. 17; <ref-ruling> consid. 2.1 p. 219 ; arrêt 8C_428/2012 du 14 novembre 2012, consid. 5.3).
4. 4.1 De manière constante, la Chambre administrative de la Cour de justice a considéré que la LPAC, à son art. 31, prévoit le versement d'une indemnité, non pas dans le but de réparer un éventuel tort moral ou de sanctionner un licenciement abusif, mais uniquement dans celui de pallier le refus de l'employeur de réintégrer la personne qui aurait été licenciée à tort (ATA/335/2012, du 5 juin 2012, consid. 4; ATA/525/2011, du 30 août 2011, consid. 7; ATA/ 413/2011 du 28 juin 2011, consid. 3; v. aussi ATA/755/2012 du 6 novembre 2012, consid. 4h et 8; jugement attaqué, consid. 8). Elle a en outre posé pour principe que les conclusions en paiement d'une indemnité sont prises en considération uniquement si la réintégration peut encore intervenir (jugement attaqué, consid. 8 in initio et les références).
4.2 Appliquant l'art. 60 let. b de la loi cantonale genevoise sur la procédure administrative (LPA/GE; RS/GE E 5 10), aux termes duquel a qualité pour recourir toute personne qui est touchée directement par une décision et a un intérêt personnel digne de protection à ce qu'elle soit annulée ou modifiée, l'autorité de recours cantonale a diversement jugé la recevabilité des prétentions d'un agent public à être indemnisé selon l'art. 31 al. 3 LPAC.
Dans le cas d'une fonctionnaire dont les rapports de service avaient été résiliés pour le 30 avril 2011 et qui avait retrouvé un emploi dès le 1er juin suivant, la Chambre administrative de la cour de justice - sans entrer en matière sur la conformité au droit de la résiliation en cause -, a déclaré irrecevables les conclusions de l'intéressée tendant au paiement d'une telle indemnité, faute d'intérêt actuel, au motif que sa réintégration n'était plus possible au moment du jugement (ATA/413/2011 du 28 juin 2011 précité). Le 21 avril 2009, le Tribunal administratif de la République et canton de Genève avait rendu un arrêt allant dans le même sens à propos d'une employée de la Ville de Genève dont l'engagement avait été résilié pour le 30 septembre 2008 et qui avait été engagée par une autre collectivité publique à compter du 1er février 2009; dans ce cas, l'intéressée prétendait être indemnisée à raison de la perte de salaire découlant de la différence entre son dernier traitement et les indemnités de chômage perçues (ATA/192/2009 ). Par la suite, la Chambre administrative a modifié cette jurisprudence. Lorsqu'il s'était écoulé un certain temps entre la fin des rapports de service résiliés de manière contraire au droit et l'entrée en fonction dans un nouvel emploi de la personne concernée, les conclusions de cette dernière ont été jugées recevables pour ce laps de temps; des indemnités, au sens de l'art. 31 LPAC, ont été allouées à raison d'un montant équivalent au dernier traitement brut, prorata temporis (ATA/525/2011 du 30 août 2011 précité, ATA/335/2012 du 5 juin 2012 précité, ATA/336/2012 du 5 juin 2012).
4.3 Ainsi, qu'elle examine une cause sous l'angle du but de la norme ou sous celui de l'intérêt pour recourir, la Chambre administrative a toujours considéré qu'une des conditions essentielles de l'octroi d'une indemnité, au sens de l'art. 31 al. 3 LPAC, était la possibilité effective pour l'agent public de réintégrer sa fonction. Cela découle d'ailleurs du texte légal dont le Tribunal fédéral a eu, au demeurant, l'occasion de relever qu'il en ressort, d'une part, que l'autorité judiciaire de recours cantonale peut renoncer à proposer la réintégration et d'autre part, que l'autorité compétente n'est pas tenue d'y procéder (arrêt 2P.181/2006 du 28 novembre 2006, consid. 2.3).
5. 5.1 En l'espèce, après la fin des rapports de service selon la résiliation litigieuse, la réintégration de l'intimée n'était plus possible puisque l'intéressée s'est trouvée à la retraite dès le lendemain de cette échéance. L'autorité de recours cantonale ne pouvait donc pas proposer une réintégration - que l'autorité compétente eût été libre de refuser - ni même présumer le rejet de cette proposition, comme elle l'a fait dans les cas (cités au consid. 4.2 ci-dessus) où le fonctionnaire avait retrouvé un emploi au moment du jugement. Les premiers juges ont d'ailleurs expressément relevé, dans les considérants de l'arrêt entrepris, que le cas de l'intimée différait de celui du fonctionnaire licencié de manière contraire au droit et qui peut encore retrouver un emploi équivalent. Dès lors, l'indemnité litigieuse paraît avoir été octroyée à l'intimée sans qu'aient été respectés ni les dispositions de l'art. 31 LPAC, ni les principes jurisprudentiels développés par l'autorité judiciaire cantonale à leur sujet.
Pour ce faire, les premiers juges semblent avoir pris en considération deux éléments qui n'apparaissent pas clairement établis: l'intimée aurait été obligée d'accepter sa mise à la retraite anticipée, (point contesté par les recourants) et elle aurait subi de la sorte un préjudice financier égal à la différence entre son dernier traitement brut et sa rente de vieillesse, sans prise en considération d'éventuels avantages compensatoires. Le raisonnement juridique sur lequel s'est fondée la cour cantonale pour s'écarter des règles légales et jurisprudentielles susmentionnées, n'est, quant à lui, nullement exposé dans le jugement entrepris. En effet, les premiers juges se limitent à justifier leur solution en qualifiant de choquante la situation de l'intimée et semblent d'ailleurs écarter un impératif d'égalité de traitement avec le fonctionnaire licencié de manière contraire au droit et qui peut retrouver un emploi équivalent.
Or, à teneur de l'<ref-law>, les décisions qui peuvent faire l'objet d'un recours devant le Tribunal fédéral doivent contenir les motifs déterminants de fait et de droit. Il résulte de cette norme que ces décisions doivent indiquer clairement les faits qui sont établis et les déductions juridiques qui sont tirées de l'état de fait déterminant. Savoir quels sont les faits déterminants revêt une importance particulière dans la mesure où le Tribunal fédéral est en principe lié par ceux constatés par la dernière instance cantonale. Un état de fait insuffisant empêche l'application des règles de droit pertinentes à la cause. Un tel manquement constitue donc une violation du droit. Si une décision attaquée ne satisfait pas aux exigences fixées à l'<ref-law>, le Tribunal fédéral peut soit la renvoyer à l'autorité cantonale en invitant celle-ci à la parfaire, soit l'annuler (<ref-law>; <ref-ruling> consid. 8.2 p. 153). Lorsqu'il décide si un jugement entaché de tels vices doit être simplement annulé ou si la cause doit de plus être renvoyée à l'instance précédente, le Tribunal fédéral respecte le principe de la bonne foi découlant de l'art. 9 Cst. selon lequel aucune partie ne doit subir de préjudice du fait de l'irrégularité en question (EHRENZELLER, in Basler Kommentar, Bundesgerichtsgesetz, 2ème éd. 2011, no 17 ad art. 112, p. 1477).
5.2 En l'espèce, comme cela a déjà été relevé, le Tribunal fédéral n'est pas en mesure de statuer. Il y a dès lors lieu de constater que la décision attaquée ne contient pas les motifs déterminants de fait et de droit requis par l'<ref-law>, si bien qu'elle doit être annulée et la cause renvoyée à l'autorité cantonale en application de l'<ref-law>.
6. La cause étant tranchée, la requête d'effet suspensif devient sans objet.
7. Dès lors que les vices de la décision sont imputables à la Chambre administrative de la Cour de justice, il convient de rendre l'arrêt sans frais (art. 66 al. 1 in fine LTF). Bien qu'ils obtiennent gain de cause, les recourants n'ont pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis en ce sens que le jugement du 21 août 2012 de la Cour de justice de la République et canton de Genève, Chambre administrative, est annulé, la cause lui étant renvoyée pour nouvelle décision au sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lucerne, le 5 mars 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Juge présidant: Ursprung
La Greffière: Berset