Faits :
A.
Le 3 novembre 2015, un appel à candidatures pour l'attribution d'une concession d'occupation du domaine public en vue de l'exploitation d'un système de vélos en libre-service sous l'appellation "A._" est paru dans la Feuille d'avis officielle de la République et canton de Genève (ci-après: la FAO), sous la rubrique "marchés publics". L'objectif annoncé était de sélectionner un concessionnaire unique qui mettrait en oeuvre un système de vélos en libre-service au sein du périmètre de la concession. L'appel à candidatures indiquait que ladite concession, d'une durée de sept ans, ne serait pas soumise à l'Accord intercantonal sur les marchés publics (AIMP) ni aux traités internationaux sur les marchés publics. Les dossiers de candidatures devaient parvenir à l'entité organisatrice X._ SA au plus tard le 12 janvier 2016.
B.
Le 13 novembre 2015, la société Y._ SA, qui a pour but le développement et la commercialisation du système de vélos en libre service "B._", a saisi la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice) d'un recours dirigé contre la société X._ SA, le Département de l'environnement, des transports et de l'agriculture de la République et canton de Genève, la Ville de Genève, ainsi que les communes de Carouge, Lancy, Onex, Plan-les-Ouates et Vernier. Elle demandait l'annulation de l'appel à candidatures susmentionné, notamment au motif que la législation sur les marchés publics serait applicable, et l'octroi de l'effet suspensif au recours.
Par décision du 22 décembre 2015, la Cour de justice a partiellement admis la requête de mesures provisionnelles formée par Y._ SA, faisant interdiction à X._ SA de procéder à l'ouverture des offres reçues en réponse à l'appel à candidatures pour l'attribution d'une concession d'occupation du domaine public et de procéder à l'évaluation de ces mêmes offres. La page de garde de la décision désignait en qualité de parties Y._ SA, d'une part, et X._ SA, ainsi que le Conseil d'Etat, d'autre part. La décision a été communiquée, par l'intermédiaire de leurs mandataires respectifs, aux parties figurant sur la page de garde et aux six communes visées dans le recours.
C.
Par acte du 25 janvier 2016, le Conseil d'Etat de la République et canton de Genève, X._ SA, la Ville de Carouge, la Ville de Genève, la Ville de Lancy, la Ville d'Onex, la Commune de Plan-les-Ouates et la Ville de Vernier ont interjeté un recours en matière de droit public et un recours constitutionnel subsidiaire au Tribunal fédéral. Sous suite de frais et dépens, ils demandent en substance au Tribunal fédéral, préalablement, d'annuler la décision attaquée et d'accorder l'effet suspensif au recours, puis cela fait et statuant à nouveau, principalement, de constater que la législation sur les marchés publics n'est pas applicable à l'appel à candidatures du 3 novembre 2015 et que le recours interjeté par Y._ SA devant l'instance précédente est irrecevable. Ils concluent également au rejet de la requête d'effet suspensif et de mesures provisionnelles formée par Y._ SA. Subsidiairement, ils requièrent le renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants.
La Cour de justice déclare persister dans sa décision. Dans ses déterminations, Y._ SA conclut, principalement, à l'irrecevabilité du recours, subsidiairement à son rejet.
Par ordonnance du 7 mars 2016, le Président de la IIe Cour de droit public a rejeté la demande d'effet suspensif au recours.

Considérant en droit :
1.
Le Tribunal fédéral examine librement et avec une pleine cognition la recevabilité des recours portés devant lui (<ref-law>; <ref-ruling> consid. 1 p. 44).
1.1. La décision attaquée est une décision sur mesures provisionnelles, par laquelle il a été fait interdiction à X._ SA de procéder à l'ouverture et à l'évaluation des offres reçues en réponse à l'appel à candidatures pour l'attribution d'une concession d'occupation du domaine public, publié dans la FAO du 3 novembre 2015.
1.2. Le prononcé attaqué constitue dès lors une décision incidente au sens de l'<ref-law> (cf. <ref-ruling> consid. 1.2 p. 79 sur l'effet suspensif; arrêt 2C_611/2011 du 16 décembre 2011 consid. 2 sur les mesures provisionnelles). Ne concernant ni la compétence ni une demande de récusation (cf. <ref-law>), elle ne peut faire séparément l'objet d'un recours au Tribunal fédéral, qu'il s'agisse d'un recours ordinaire ou d'un recours constitutionnel subsidiaire (<ref-law>), qu'aux conditions prévues à l'<ref-law>. Selon cette disposition, les décisions préjudicielles ou incidentes peuvent faire l'objet d'un recours immédiat au Tribunal fédéral dans deux cas de figure, à savoir si elles sont propres à causer un préjudice irréparable (let. a) 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 (let. b). Cette seconde hypothèse n'est à l'évidence pas remplie en l'espèce. En effet, le recours porte sur l'interdiction de procéder à l'ouverture et à l'évaluation des offres durant la procédure et, par conséquent, ne concerne pas le fond du litige, de sorte que son admission ne saurait mettre fin à la procédure au fond. La recevabilité du recours est donc subordonnée à l'existence d'un préjudice irréparable au sens de l'<ref-law> (cf. arrêts 2D_43/2015 du 10 décembre 2015 consid. 1.1; 2C_611/2011 du 16 décembre 2011 consid. 2).
2.
2.1. Le préjudice irréparable conformément à l'<ref-law> doit être de nature juridique et ne pas pouvoir être ultérieurement réparé par une décision finale favorable au recourant (<ref-ruling> consid. 2.2.1 p. 317 et les arrêts cités). Un dommage de pur fait, comme la prolongation de la procédure ou un accroissement des frais de celle-ci, n'est pas suffisant (<ref-ruling> consid. 2.4 p. 104; <ref-ruling> consid. 2.2.1 p. 317). Il appartient au recourant d'expliquer en quoi la décision incidente qu'il attaque remplit les conditions de l'<ref-law> (<ref-ruling> consid. 1.2 p. 429 et les arrêts cités), à moins que celles-ci ne fassent d'emblée aucun doute (<ref-ruling> consid. 4 p. 95).
2.2. Avant d'examiner les arguments soulevés par les recourants, il convient de rappeler les dispositions pertinentes applicables à l'utilisation du domaine public dans le canton de Genève.
Selon l'art. 13 al. 2 de la loi genevoise sur le domaine public (LDPu; RS/GE L 1 05), l'établissement de constructions ou d'installations permanentes ou non permanentes sur le domaine public, son utilisation à des fins industrielles ou commerciales ou toute autre occupation de celui-ci excédant l'usage commun sont subordonnés à une permission. Ils sont subordonnés à une concession s'ils sont assortis de dispositions contractuelles (art. 13 al. 2 LDPu), étant précisé que le Conseil d'Etat est compétent pour octroyer les concessions d'une durée inférieure à 25 ans (art. 16 al. 2 LDPu). Les permissions sont accordées par l'autorité cantonale ou communale qui administre le domaine public (art. 15 LDPu). L'art. 19 al. 1 LDPu précise que les permissions sont délivrées à titre précaire. Elles peuvent être retirées sans indemnité pour de justes motifs, notamment si l'intérêt général l'exige (art. 19 al. 2 LDPu).
2.3. Les recourants estiment que la décision attaquée leur cause un préjudice irréparable pour plusieurs raisons. Tout d'abord, dans la mesure où la décision empêche l'octroi de toute concession de vélos en libre-service dans le périmètre défini par l'appel à candidatures contesté, l'intimée aurait le temps de s'installer dans le canton et développerait un réseau de vélos en libre-service avec la collaboration de quelques communes qui auraient délivré des permissions ou seraient sur le point de le faire en considérant que l'octroi d'une concession n'est pas nécessaire. Il pourrait en résulter l'occupation de fait d'une partie importante du domaine public par une entreprise qui bénéficierait d'un avantage concurrentiel indu par rapport à toutes autres entreprises qui voudraient s'installer. La décision attaquée serait donc de nature à créer une distorsion de concurrence. En outre, selon les recourants, tant que l'Etat ne peut pas octroyer la concession litigieuse, d'autres entreprises pourraient prétendre à l'octroi d'une permission d'utilisation du domaine public, sans coordination possible. Ils soutiennent que cela pourrait aboutir à la présence de plusieurs entreprises concurrentes, ayant des systèmes incompatibles entre eux, alors qu'ils estiment qu'un seul système de vélos en libre-service devrait se déployer sur l'ensemble du canton, ce que seul l'octroi de concessions permettrait d'assurer. Par ailleurs, l'arrêt attaqué interdisant à l'entité organisatrice d'ouvrir les candidatures reçues, le Conseil d'Etat ne peut pas prendre connaissance des solutions proposées. Or, selon les recourants, s'il était saisi d'une demande d'octroi de concession portant sur un périmètre voisin, il pourrait être amené à devoir autoriser un système incompatible avec celui qui sera installé dans le périmètre concerné. Enfin, la décision attaquée porterait atteinte à la réputation des recourants puisqu'elle serait de nature à remettre en cause leur crédibilité.
2.4. Ces arguments ne sont pas convaincants.
S'agissant du risque quant à leur réputation invoqué par les recourants, celui-ci est purement théorique et ne saurait être considéré comme un préjudice irréparable de nature juridique au sens de l'<ref-law>. Il en va de même pour la prétendue distorsion de concurrence qu'engendrerait une éventuelle installation progressive de l'intimée sur le territoire des communes genevoises. En effet, dans la mesure où les six communes visées se prononcent en faveur d'un système de concession et déclarent ne pas vouloir accorder une simple permission (cf. p. 11 du recours), on voit mal comment l'intimée pourrait s'installer dans les six communes concernées. S'agissant des autres communes du canton, celles-ci ne sont pas comprises dans le périmètre visé par l'appel à candidatures litigieux, de sorte que le prononcé attaqué n'a aucune incidence sur leur pouvoir décisionnel. En effet, elles conservent le droit et la liberté d'accorder des permissions d'utilisation du domaine public à tout exploitant de systèmes de vélos en libre-service, y compris à l'intimée, quelle que soit l'issue de la présente procédure. En tout état de cause, s'il devait en résulter une distorsion de concurrence, comme le prétendent les recourants, celle-ci serait la conséquence de l'autonomie accordée aux communes s'agissant de l'administration de leur domaine public, et non celle de la décision entreprise.
Pour ce même motif, les recourants ne peuvent être suivis lorsqu'ils affirment que la suspension de la procédure litigieuse empêcherait la coordination entre les systèmes de vélos en libre-service pour l'ensemble du canton. En effet, dès lors que l'octroi de la concession litigieuse vise à mettre en place un système de vélos en libre-service uniquement sur le territoire des six communes recourantes, les autres communes du canton demeurent en tout état de cause libres de délivrer de simples permissions pour autoriser l'exploitation d'un système de vélos en libre-service différent. Autrement dit, et contrairement à ce que soutiennent les recourants, l'octroi de la concession litigieuse ne permet pas d'assurer une coordination entre les systèmes de vélos en libre-service pour l'ensemble du territoire cantonal. Pour le surplus, il y a lieu de rappeler que si des permissions étaient délivrées, elles le seraient à titre précaire, conformément aux dispositions précitées, et pourraient donc être retirées pour des motifs d'intérêt général.
2.5. Compte tenu de ce qui précède, la décision attaquée qui interdit à l'entité organisatrice de procéder à l'ouverture des offres reçues et à l'évaluation de celles-ci n'entraîne aucun préjudice irréparable pour les recourants. Aucune des conditions posées par l'<ref-law> n'étant réalisées, le recours est irrecevable. Il n'y a donc pas lieu d'examiner les autres conditions de recevabilité.
2.6. L'intimée, qui obtient gain de cause avec l'assistance d'un avocat, a droit à des dépens à la charge des recourants (art. 68 al. 1 et 2 LTF). Il n'y a pas lieu de percevoir des frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est irrecevable.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de 2'000 fr., à payer à l'intimée, est mise à la charge des recourants solidairement entre eux.
4.
Le présent arrêt est communiqué aux mandataires des recourants et de l'intimée et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lausanne, le 30 juin 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Petry