Faits :
A.
A.a. A._ (ci-après: l'employée), née en 1976, a été engagée par les Hôpitaux universitaires de Genève (ci-après: les HUG ou l'employeur) en tant qu'aide en soins et accompagnement, à un taux d'activité de 80 %, par contrat de durée déterminée du 1 er juillet 2014 au 30 juin 2015. Du 1 er juillet 2015 au 20 mars 2016, elle a été placée aux HUG par une agence intérimaire et y a effectué plusieurs missions de durée variable dans différentes unités. Le 29 novembre 2017, elle a été engagée par les HUG en tant qu'aide en soins et accompagnement, à un taux d'activité de 80 %, pour une durée indéterminée dès le 1 er janvier 2018. Le temps d'essai était de trois mois. Elle a commencé son activité le 2 janvier 2018 au sein de l'unité B._ de l'hôpital C._ (ci-après: l'unité B._).
A.b. Le 16 janvier 2018, un entretien de bilan intermédiaire s'est tenu entre l'employée et D._, infirmière responsable de l'unité B._. Selon le document signé à cette occasion par les précitées, l'employée rencontrait de "grandes difficultés à remplir les objectifs"; un nouvel entretien était fixé au 31 janvier 2018 à 13h30 pour faire le point sur l'atteinte des objectifs.
Selon l'employeur, un nouvel entretien a bien eu lieu le 31 janvier 2018 entre D._ et l'employée, ce que cette dernière conteste. La cour cantonale a retenu que l'employeur - qui a produit un document non signé intitulé "Document élaboré le 31/01 par Mme D._, IRES unité B._" (ci-après: document du 31 janvier 2018) - n'avait pas démontré à satisfaction de droit qu'un tel entretien avait eu lieu, ce que les HUG critiquent devant le Tribunal fédéral (cf. consid. 2 infra).
A.c. Selon le document du 31 janvier 2018, un nouvel entretien était fixé au 1 er février 2018 avec E._ (infirmière assistante de la responsable des soins), F._ (responsable des ressources humaines) et D._ afin d'évoquer la poursuite de la collaboration.
Le 1 er février 2018, un entretien d'évaluation et de développement des compétences (ci-après: EEDC) s'est tenu pour la période d'un mois. Selon le document signé à cette occasion par l'employée, par D._ et par E._, auquel était joint le bilan intermédiaire du 16 janvier 2018, l'évaluation globale était inacceptable et la poursuite de la collaboration était exclue au motif de prestations insuffisantes.
A.d. Le 1 er février 2018, sur la base des entretiens des 16 janvier 2018 et 1 er février 2018, les HUG ont résilié le contrat de travail de l'employée pour le 18 février 2018 en raison de l'insuffisance de ses prestations professionnelles. Il était précisé que lors des entretiens, elle avait eu tout loisir de s'exprimer à ce sujet, de sorte que son droit d'être entendue avait été respecté. Cette décision, signée par G._, directeur des ressources humaines ad interim, lui a été remise en main propre le jour même.
B.
Statuant sur recours de l'employée, la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après la Chambre administrative) a constaté par jugement du 12 mars 2019 que la décision de résiliation des rapports de service du 1 er février 2018 était contraire au droit, a proposé la réintégration de l'employée au sein des HUG et, en cas de refus de l'employeur de procéder à cette réintégration, lui a ordonné de transmettre immédiatement sa décision à la Chambre administrative.
C.
Les HUG interjettent un recours en matière de droit public contre ce jugement, en concluant principalement à son annulation et à la constatation que la décision de résiliation des rapports de service du 1 er février 2018 est conforme au droit, et subsidiairement au renvoi de la cause à la cour cantonale pour qu'elle statue dans le sens des considérants. Ils sollicitent en outre l'octroi de l'effet suspensif.
La juridiction cantonale a renoncé à se déterminer. L'intimée a conclu au rejet du recours et a sollicité le bénéfice de l'assistance judiciaire. Les recourants ont répliqué.
D.
Par ordonnance du 10 juillet 2019, la juge instructrice a admis la requête d'effet suspensif.

Considérant en droit :
1.
1.1. Les HUG sont un établissement cantonal de droit public doté de la personnalité juridique (art. 1 al. 1 et art. 5 al. 1 de la loi du canton de Genève du 19 septembre 1980 sur les établissements publics médicaux [LEPM; RS/GE K 2 05]). Leur personnel est en principe soumis à la loi générale du canton de Genève du 4 décembre 1997 relative au personnel de l'administration cantonale, du pouvoir judiciaire et des établissements publics médicaux (LPAC; RS/GE B 5 05). Le jugement entrepris a donc été rendu en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF. Dans la mesure où la contestation porte sur la résiliation de tels rapports, il s'agit d'une contestation de nature pécuniaire (voir p. ex. arrêt 8C_740/2017 du 25 juin 2018 consid. 1), de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. Vu que la contestation porte potentiellement sur le salaire de plusieurs mois, respectivement - selon les conclusions prises par l'employée devant la juridiction cantonale - sur l'octroi d'une indemnité correspondant à six mois de salaire, la valeur litigieuse atteint le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public en ce domaine (art. 51 al. 2 et 85 al. 1 let. b LTF).
1.2. Le recours est recevable contre les décisions finales, à savoir contre les décisions qui mettent fin à la procédure (<ref-law>), et contre les décisions partielles, soit celles qui statuent sur un objet dont le sort est indépendant de celui qui reste en cause (<ref-law>) ou qui mettent fin à la procédure à l'égard d'une partie des consorts (<ref-law>). Les décisions préjudicielles et incidentes autres que celles concernant la compétence ou les demandes de récusation (cf. <ref-law>) ne peuvent faire l'objet d'un recours que si elles peuvent causer un préjudice irréparable (<ref-law>) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (<ref-law>). En règle générale, une décision de renvoi ne met pas fin à la procédure (<ref-ruling> consid. 1.2 p. 283; <ref-ruling> consid. 2 p. 294; <ref-ruling> consid. 4.2 p. 482) et n'est pas non plus de nature à causer un préjudice irréparable aux parties, le seul allongement de la durée de la procédure ou le seul fait que son coût s'en trouve augmenté n'étant pas considéré comme constitutif d'un tel dommage (ATF <ref-ruling> précité consid. 5.2.1 et 5.2.2 p. 483).
En l'espèce, le jugement attaqué, qui constate que la décision de résiliation des rapports de service des HUG du 1 er février 2018 est contraire au droit et propose la réintégration de l'employée au sein des HUG, s'analyse comme une décision à tout le moins potentiellement finale. Ce n'est en effet qu'en cas de décision négative des HUG sur la proposition de réintégration que la Chambre administrative sera ressaisie de l'affaire, conformément à l'art. 31 al. 4 LPAC (cf. consid. 3.3 infra; cf. arrêt 8C_430/2011 du 12 avril 2012, dans lequel la cour de céans est entrée en matière sur le recours dans une situation identique).
1.3. Pour le surplus, interjeté dans les formes requises et en temps utile, le recours respecte les exigences des art. 42 et 100 al. 1 LTF. Il sied ainsi d'entrer en matière.
2.
2.1. Le Tribunal fédéral, qui est un juge du droit, fonde son raisonnement juridique sur les faits retenus par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2 p. 190) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). L'appréciation des preuves est arbitraire lorsqu'elle est manifestement insoutenable, en contradiction avec le dossier, ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des conclusions insoutenables (<ref-ruling> consid. 2.3 p. 266 et les références citées).
2.2. Les juges cantonaux ont retenu que l'employeur n'avait pas démontré à satisfaction de droit qu'un entretien avait eu lieu le 31 janvier 2018 entre D._ et l'employée. Ils ont relevé que contrairement à celui du 16 janvier 2018, le document du 31 janvier 2018 n'était signé ni par l'employée ni par D._. Si cette dernière avait déclaré, lors de son audition en qualité de témoin, que le document en question, signé par l'employée, devait être dans son dossier, l'employeur ne l'avait pas produit à l'appui de ses conclusions après enquêtes. Par ailleurs, la seule annexe de l'EEDC du 1 er février 2018 était le bilan intermédiaire du 16 janvier 2018 et la case de cet EEDC prévue pour le "Point de vue du collaborateur" était vide, ce qui renforçait le constat qu'aucun entretien n'avait eu lieu le 31 janvier 2018. De même, la lettre de résiliation du 1 er février 2018 se limitait à faire mention des entretiens du 16 janvier 2018 et du 1 er février 2018, sans faire référence à un quelconque entretien qui aurait eu lieu le 31 janvier 2018.
2.3. Les recourants ne démontrent pas en quoi cette appréciation des preuves serait arbitraire. Il est constant qu'il incombait à l'employeur d'établir la tenue - contestée par l'employée - de l'entretien allégué du 31 janvier 2018. Or cette preuve n'est pas rapportée par la seule production du document du 31 janvier 2018 ne comportant - contrairement à celui du 16 janvier 2018 - aucune signature sous les noms "Mme A._" et "Mme D._" dactylographiés en bas de page. Le fait que le bilan intermédiaire du 16 janvier 2018 mentionnait qu'un nouvel entretien était fixé au 31 janvier 2018 à 13h30 pour faire le point sur l'atteinte des objectifs n'établit pas qu'un nouvel entretien ait effectivement eu lieu à cette date, d'autant moins qu'un tel entretien n'est mentionné ni dans l'EEDC du 1 er février 2018 - dont la seule annexe était le bilan intermédiaire du 16 janvier 2018 - ni dans la lettre de résiliation du 1 er février 2018. Quant au fait que D._ ait confirmé avoir eu un entretien avec l'employée le 31 janvier 2018 lorsqu'elle a été entendue en qualité de témoin et, à ce titre, rendue attentive aux sanctions que l'<ref-law> attache au faux témoignage, il n'est pas davantage déterminant. On ne saurait affirmer, comme le font les recourants, que D._ n'avait aucun intérêt personnel à la procédure, dès lors que c'est sur la base de son appréciation que l'employeur a décidé de licencier l'employée. Par ailleurs, le risque d'une condamnation pour faux témoignage était purement théorique au vu de l'impossibilité d'apporter dans la procédure pénale la preuve qu'aucun entretien n'a eu lieu le 31 janvier 2018.
3.
3.1. La cour cantonale a ainsi retenu - sans arbitraire (cf. consid. 2.3 supra) - que l'employée avait été reçue le 1 er février 2018 pour son EEDC, dont la conclusion était, au vu des prestations insuffisantes, l'exclusion de la poursuite de la collaboration. À l'issue de cet entretien ou peu après qu'elle avait été conduite dans le bureau des ressources humaines, le courrier de résiliation des rapports de service lui avait été remis en main propre. L'employée ignorait jusqu'au 1 er février 2018 que l'employeur envisageait de la licencier. S'il est vrai qu'elle était en temps d'essai au moment de son licenciement, ce qui selon la jurisprudence laissait une grande liberté d'appréciation à l'employeur de mettre fin aux rapports de service, ce dernier n'en devait pas moins respecter son droit d'être entendue. Or, en procédant à un EEDC le 1 er février 2018 et en lui remettant un courrier de résiliation des rapports de service à son issue ou très peu de temps après, l'employeur n'avait pas laissé à l'employée la possibilité de faire valoir son point de vue et avait donc violé son droit d'être entendue.
3.2. La cour cantonale a précisé que le Tribunal fédéral avait certes reconnu que l'atteinte aux droits procéduraux d'une collaboratrice qui se trouvait en temps d'essai ne pouvait pas être qualifiée de grave vu la grande liberté d'appréciation reconnue aux parties pour mettre fin aux rapports de service pendant cette période et que le vice pouvait être réparé devant les instances judiciaires cantonales. Toutefois, à Genève, les juridictions administratives ne pouvaient pas revoir l'opportunité d'une décision (art. 61 al. 2 LPA [Loi du 12 septembre 1985 sur la procédure administrative; RS/GE E 5 10]). Il était dès lors exclu d'envisager une réparation du droit d'être entendu devant la Chambre administrative dans le contexte d'une résiliation des rapports de service, faute pour cette dernière de disposer d'un pouvoir d'examen équivalent à celui de l'autorité qui avait prononcé le licenciement, dans un domaine où un large pouvoir d'appréciation était reconnu à l'autorité administrative. Les juges cantonaux ont considéré que dans ces circonstances, les HUG avaient violé gravement le droit d'être entendue de leur employée et que ce vice n'était pas réparable devant la juridiction de recours.
3.3. Selon l'art. 31 LPAC, si la Chambre administrative 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. 3). En cas de décision négative de l'autorité compétente ou en cas de refus du recourant, la Chambre administrative fixe une indemnité dont le montant ne peut pas être supérieur - concernant un employé - à six mois du dernier traitement brut (al. 4). En l'espèce, la Chambre administrative, relevant que la résiliation des rapports de service était contraire au droit et qu'il ne ressortait pas des écritures des HUG que ceux-ci s'opposaient catégoriquement à la réintégration de l'employée, a décidé de proposer la réintégration de l'employée au sein des HUG et a précisé qu'en cas de refus, il appartiendrait à ceux-ci de lui transmettre immédiatement copie de sa décision afin qu'elle puisse se ressaisir de l'affaire, conformément à l'art. 31 al. 4 LPAC.
4.
4.1. Il est constant qu'en tant que membre du personnel des HUG, l'intimée est soumise à LPAC et au Statut du personnel des HUG (ci-après: le Statut). Selon l'art. 4 al. 1 LPAC, le personnel de la fonction publique se compose de fonctionnaires, d'employés, d'auxiliaires, d'agents spécialisés et de personnel en formation. Est un fonctionnaire le membre du personnel régulier ainsi nommé pour une durée indéterminée après avoir accompli comme employé une période probatoire (art. 5 LPAC). Est un employé le membre du personnel régulier qui accomplit une période probatoire (art. 6 al. 1 LPAC). Pendant le temps d'essai et la période probatoire, chacune des parties peut mettre fin aux rapports de service; le membre du personnel n'ayant pas qualité de fonctionnaire est entendu par l'autorité compétente; il peut demander que le motif de résiliation lui soit communiqué (art. 21 al. 1 LPAC). Pendant le temps d'essai, d'une durée de trois mois au plus, le délai de résiliation est de quinze jours pour la fin d'une semaine (art. 20 al. 1 LPAC).
4.2. L'obligation d'entendre un employé avant qu'une décision de licenciement soit prise, rappelée à l'art. 21 al. 1 LPAC, découle du respect de son droit être entendu garanti par l'art. 29 al. 2 Cst. et implique qu'en cas de résiliation des rapports de service, le collaborateur dispose de suffisamment de temps pour préparer ses objections (arrêt 8C_410/2018 du 5 février 2019 et les références citées). Lorsqu'il contrôle l'application du droit d'être entendu sous l'angle de l'art. 29 al. 2 Cst., le Tribunal fédéral en détermine le contenu et la portée en fonction de la situation concrète et des intérêts en présence. Doivent en particulier être prises en considération, d'une part, l'atteinte aux intérêts de l'administré, telle qu'elle résulte de la décision à prendre et, de l'autre, l'importance et l'urgence de l'intervention administrative. D'une manière générale, plus la décision envisagée est de nature à porter gravement atteinte aux intérêts de l'administré, plus le droit d'être entendu de ce dernier doit être accordé et reconnu largement. En outre, il y a lieu de tenir compte des garanties que la procédure offre globalement à l'intéressé pour sa défense. En particulier, on se montrera généralement moins exigeant avec le strict respect du droit d'être entendu si la possibilité existe de porter la contestation devant une autorité de recours disposant d'un libre pouvoir d'examen, à condition toutefois que la violation ne soit pas particulièrement grave (<ref-ruling> consid. 2.3 p. 282 et les arrêts cités; arrêt 8C_310/2017 du 14 mai 2018 consid. 7.2).
4.3. Le Tribunal fédéral considère qu'en matière de rapports de travail de droit public, des occasions relativement informelles de s'exprimer avant le licenciement peuvent remplir les exigences du droit constitutionnel d'être entendu, pour autant que la personne concernée ait compris qu'une telle mesure pouvait entrer en ligne de compte à son encontre (arrêts 8C_310/2017 précité consid. 7.4; 8C_541/2017 du 14 mai 2018 consid. 2.2; 8C_301/2017 du 1 er mars 2018 consid. 3.2 et les arrêts cités). La personne concernée ne doit pas seulement connaître les faits qui lui sont reprochés, mais doit également savoir qu'une décision allant dans une certaine direction est envisagée à son égard (<ref-ruling> consid. 5.3 p. 17; arrêt 8C_158/2009 du 2 septembre 2009 consid. 5.2, non publié in <ref-ruling>). Le droit d'être entendu doit par principe s'exercer avant le prononcé de la décision (<ref-ruling> consid. 2.3 p. 222). Ainsi, il n'est pas admissible, sous l'angle du droit d'être entendu, de remettre à l'employé une décision de résiliation des rapports de service en se contentant de lui demander de s'exprimer s'il le désire (arrêts 8C_541/2017 précité consid. 2.2; 8C_419/2017 du 16 avril 2018 consid. 4.3.1; 8C_301/2017 précité consid. 3.2 et les références citées).
4.4. Dans une affaire genevoise dans laquelle un employé d'une fondation de droit public avait été licencié pendant le temps d'essai au motif qu'il ne correspondait pas au profil requis, le Tribunal fédéral a considéré qu'il n'y avait pas de raison de s'écarter des constatations de la cour cantonale selon lesquelles l'employé avait eu l'occasion de s'exprimer lors de l'entretien qui avait eu lieu avant que la décision de licenciement lui fût remise le même jour en main propre. Si le jugement attaqué ne disait rien sur la durée de l'entretien et son déroulement, l'employé se trouvait en période d'essai, pour laquelle les statuts de la fondation ne prévoyaient pas de motif de licenciement, de sorte qu'une éventuelle violation de son droit d'être entendu n'aurait su revêtir un caractère de gravité tel qu'il aurait empêché toute réparation devant une instance jouissant d'un plein pouvoir d'examen en fait et en droit (arrêt 8C_419/2017 précité consid. 4.3.2). Une réparation, devant deux instances cantonales disposant d'un plein pouvoir d'examen, de la violation du droit d'être entendue d'une employée licenciée pendant le temps d'essai a également été admise dans une affaire vaudoise, vu la grande liberté d'appréciation reconnue aux parties de mettre fin aux rapports de service pendant le temps d'essai (arrêt 8C_310/2017 précité consid. 7.6).
5.
5.1. Les recourants reprochent à la cour cantonale d'avoir considéré qu'en procédant à un EEDC le 1 er février 2018 et en remettant à l'intimée un courrier de résiliation des rapports de service à son issue ou très peu de temps après, ils ne lui avaient pas laissé la possibilité de faire valoir son point de vue et avaient donc violé son droit d'être entendue. Ils lui font en outre grief d'avoir retenu que cette violation était grave et non réparable devant la juridiction de recours.
5.2. Il ressort des constatations de fait du jugement attaqué qu'à l'occasion d'un entretien de bilan intermédiaire, le 16 janvier 2018, il a été relevé que l'employée rencontrait de "grandes difficultés à remplir les objectifs". Par la suite, l'employée a participé le 1 er février 2018 à un EEDC dont il est ressorti que l'évaluation globale était inacceptable et que la poursuite de la collaboration était exclue au motif de prestations insuffisantes. A l'issue de cet entretien ou très peu de temps après, elle s'est vu remettre en main propre une décision de licenciement, signée par le directeur des ressources humaines ad interim, en raison de l'insuffisance de ses prestations professionnelles. La question de savoir si le droit d'être entendue de l'intimée a été respecté par la possibilité de s'exprimer lors de l'EEDC qui a eu lieu avant que la décision de licenciement lui soit remise peut rester indécise. En effet, dans tous les cas, une éventuelle violation du droit d'être entendue de l'intimée, qui a été licenciée après le premier mois de sa période d'essai de trois mois, ne saurait revêtir un caractère de gravité tel qu'il empêcherait toute réparation devant une instance jouissant d'un plein pouvoir d'examen (cf. consid. 4.4 supra). La possibilité de guérir un tel vice ne suppose pas que l'autorité de recours ait la compétence d'apprécier l'opportunité de la décision attaquée, mais bien qu'elle dispose d'un pouvoir d'examen complet en fait et en droit (<ref-ruling> consid. 4.4 p. 174; <ref-ruling> consid. 2.3.2 p. 197). Or tel est le cas de la Chambre administrative de la Cour de justice de la République et canton de Genève (art. 61 al. 1 LPA/GE; arrêt 8C_541/2017 précité consid. 2.5 et les références citées).
5.3. Il s'ensuit que le jugement attaqué doit être annulé et la cause renvoyée à la Chambre administrative, en admission des conclusions subsidiaires prises par les recourants, pour nouvelle décision.
6.
Conformément à sa demande, l'intimée, qui satisfait aux conditions de l'<ref-law>, est dispensée de payer des frais judiciaires. Quant aux conditions auxquelles l'<ref-law> subordonne la désignation d'un avocat d'office, elles sont également réalisées. L'attention de l'intéressée est toutefois attirée sur le fait qu'elle devra rembourser la caisse du Tribunal si elle devient en mesure de le faire ultérieurement (<ref-law>). Bien qu'ils obtiennent gain de cause et qu'ils soient représentés par un avocat, les recourants n'ont pas droit à des dépens (<ref-law>; arrêt 8C_151/2010 du 31 août 2010 consid. 6.2 et les références citées).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis. Le jugement de la Chambre administrative de la Cour de justice de la République et canton de Genève du 12 mars 2019 est annulé. La cause est renvoyée à l'autorité précédente pour nouvelle décision. Le recours est rejeté pour le surplus.
2.
La requête d'assistance judiciaire de l'intimée est admise et Me Christian Dandrès lui est désigné comme avocat d'office.
3.
Les frais judiciaires, arrêtés à 1000 fr., sont mis à la charge de l'intimée. Ils sont toutefois supportés provisoirement par la caisse du Tribunal fédéral.
4.
Une indemnité de 2800 fr., supportée provisoirement par la caisse du Tribunal fédéral, est allouée à Me Dandrès à titre d'honoraires.
5.
Le présent arrêt est communiqué aux parties et à la Chambre administrative de la Cour de justice de la République et canton de Genève.
Lucerne, le 12 mai 2020
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
Le Greffier : Ourny