Faits:
A. Le 11 novembre 1983, le Grand Conseil de la République et canton de Genève a adopté la loi cantonale genevoise en matière de chômage (RS GE J 2 20). Cette loi a été modifiée la dernière fois par la loi 9922 adoptée par le Grand Conseil le 28 juin 2007. A la suite de l'aboutissement d'un référendum, la loi modifiée a été adoptée en votation populaire le 16 décembre 2007. Elle est entrée en vigueur le 1er février 2008. Elle règle l'application dans le canton de Genève de la législation fédérale sur l'assurance-chômage obligatoire et l'indemnité en cas d'insolvabilité du 25 juin 1982 (LACI). Elle vise aussi, par des mesures cantonales, à favoriser le placement rapide et durable des chômeurs dans le marché de l'emploi et à renforcer les compétences des chômeurs par l'octroi de mesures d'emploi, de formation et de soutien à la réinsertion. Elle institue pour des chômeurs sans perspective de réinsertion rapide des possibilités de maintien en activité professionnelle afin de prévenir leur marginalisation (art. 1er let. b, c et e). La loi contient un nouveau chapitre VA du titre III, intitulé « Programme d'emplois de solidarité sur le marché complémentaire de l'emploi ». Ce chapitre contient les dispositions suivantes:
Art. 45D Principe (nouveau)
1 Un programme de création d'emplois sur le marché complémentaire de l'emploi est institué.
2 Il est destiné aux personnes qui ont épuisé leurs droits à l'assurance-chômage sans que les mesures prévues dans la présente loi se soient avérées fructueuses.
3 Le présent chapitre ne consacre pas un droit pour le chômeur d'obtenir une mesure déterminée.
Art. 45E Organisation (nouveau)
1 Le département organise la mise à disposition de ces emplois en mandatant à cet effet des institutions privées ou associatives, à but non lucratif, poursuivant des buts d'intérêt collectif et déployant des activités sur le marché complémentaire de l'emploi.
2 Les projets retenus doivent répondre à une utilité sociale et dégager, dans la mesure du possible, des moyens financiers propres qui permettent de couvrir tout ou partie de leurs coûts. Ils doivent viser à l'insertion professionnelle des demandeurs d'emploi.
3 Dans le choix des activités retenues, le département veille à éviter toute concurrence avec les entreprises commerciales genevoises, en particulier celles régies par des conventions collectives de travail.
4 Le département demande le préavis du Conseil de surveillance du marché de l'emploi sur les mandats attribués, les projets et les activités retenus.
Art. 45F Nombre d'emplois (nouveau)
1 L'Etat fixe, dans le cadre de l'élaboration de son budget annuel, l'enveloppe à disposition de ce programme et le nombre d'emplois de solidarité qu'il devrait permettre de créer sur le marché complémentaire de l'emploi.
2 Il consulte préalablement le Conseil de surveillance du marché de l'emploi.
Art. 45G Modalités et compensation financière (nouveau)
1 Les bénéficiaires perçoivent de la part des institutions partenaires un salaire dont le montant est au moins équivalent aux normes prévues par la loi sur les prestations cantonales accordées aux chômeurs en fin de droit, du 18 novembre 1994, ou celles découlant de la loi sur l'aide sociale individuelle, du 22 mars 2007.
2 Le Conseil d'Etat détermine des salaires minimaux sur préavis du Conseil de surveillance du marché de l'emploi.
3 Les relations contractuelles entre les bénéficiaires et les institutions partenaires sont régies pour le surplus par le contrat de travail signé par ces derniers et, à titre supplétif, par les dispositions du titre dixième du code des obligations.
4 Le contrat de travail est à durée indéterminée et donne lieu au prélèvement des cotisations sociales usuelles.
5 L'Etat contribue au paiement du salaire versé par l'institution partenaire. Cette contribution est déterminée par le département en tenant compte des moyens financiers que l'institution dégage par son activité, conformément à l'article 45E, alinéa 2, ainsi que de la situation personnelle de l'intéressé, conformément à l'alinéa 1 du présent article.
6 La contribution de l'Etat fait l'objet d'une convention entre celui-ci et l'institution concernée, qui précise les droits et obligations de chaque partie. Cette contribution n'est pas soumise à la loi sur les indemnités et les aides financières, du 15 décembre 2005.
B. Le 23 janvier 2008, le Conseil d'Etat de la République et canton de Genève a adopté le Règlement d'exécution de cette loi (Règlement d'exécution de la loi en matière de chômage; RS J 2 20.01; ci-après: le règlement). Il est paru dans la Feuille d'avis officielle de la République et canton de Genève le 30 janvier 2008. L'art. 43 du règlement fixe le salaire mensuel brut de l'emploi de solidarité. L'art. 44 prévoit, sous certaines conditions, le versement d'une allocation complémentaire en faveur du bénéficiaire d'un emploi de solidarité. Ces deux dispositions ont la teneur suivante:
Art. 43 Salaires
1 Le salaire mensuel brut de l'emploi de solidarité est de:
a) 3'000 F pour une fonction ne requérant aucune formation spécifique;
b) 3'500 F pour une fonction conforme à la lettre a, mais occupée par un titulaire du certificat fédéral de capacité ou d'un diplôme professionnel équivalent;
c) 4'000 F pour une fonction spécialisée ou à responsabilités, dont l'exercice requiert impérativement un certificat fédéral de capacité ou un diplôme professionnel équivalent.
2 Ces montants correspondent à un taux d'activité à plein temps sur la base de 40 heures hebdomadaires et 12 versements par an.
3 L'office détermine le salaire adéquat après examen de l'emploi de solidarité concerné, ainsi que du dossier de son bénéficiaire potentiel.
Art. 44 Allocation complémentaire
1 Si le salaire perçu par le bénéficiaire d'un emploi de solidarité est inférieur aux prestations qu'il percevrait en vertu de la loi sur les prestations cantonales accordées aux chômeurs en fin de droit, du 18 novembre 1994, une allocation complémentaire lui est versée pour combler le différentiel constaté.
2 Cette allocation complémentaire n'est pas assimilée à un salaire et ne donne pas lieu au prélèvement des cotisations sociales.
(...)
C. Par une écriture commune remise à la Poste le 29 février 2008, la Communauté genevoise d'action syndicale (CGAS), Comedia, syndicat des médias, le Syndicat interprofessionnel des travailleuses et travailleurs (SIT), le Syndicat des services publics (SSP/VPOD), le Syndicat UNIA, ainsi que C._ ont formé un recours en matière de droit public au Tribunal fédéral contre le règlement précité, dont ils demandent l'annulation. Le Conseil d'Etat a conclu au rejet du recours. Le Secrétariat d'Etat à l'économie s'est également exprimé sur le recours.
Les parties ont maintenu leurs conclusions au terme d'un échange ultérieur d'écritures.

Considérant en droit:
1. Le règlement contesté constitue un acte normatif cantonal et ne peut faire l'objet d'aucun recours cantonal. Il est par conséquent directement attaquable par un recours en matière de droit public (art. 82 let. b et 87 al. 1 LTF), qui a par ailleurs été formé en temps utile (<ref-law>).
2.1 L'<ref-law> confère la qualité pour former un recours en matière de droit public à quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (let. a), est particulièrement atteint par la décision ou l'acte normatif attaqué (let. b) et a un intérêt digne de protection à son annulation ou à sa modification (let. c). Lorsque l'acte attaqué est un acte normatif, l'intérêt personnel requis peut être simplement virtuel; il suffit qu'il existe un minimum de vraisemblance que le recourant puisse se voir un jour appliquer les dispositions contestées (<ref-ruling> consid. 2.2 p. 289, 133 II 353 consid. 3.3. p. 358). Quant à l'intérêt digne de protection, il n'est pas nécessaire qu'il soit de nature juridique, un intérêt de fait étant suffisant (<ref-ruling> consid. 2.2 p. 290). S'agissant d'une association, elle est habilitée à recourir même si elle n'est pas directement touchée par l'acte entrepris. Il faut cependant qu'elle ait la personnalité juridique et que la défense des intérêts de ses membres figure parmi ses buts statutaires. Il faut en outre que la majorité de ses membres, ou du moins une grande partie de ceux-ci, soit personnellement touchée par l'acte attaqué (<ref-ruling> consid. 1.2.1 p. 30 et la jurisprudence citée).
2.1 L'<ref-law> confère la qualité pour former un recours en matière de droit public à quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (let. a), est particulièrement atteint par la décision ou l'acte normatif attaqué (let. b) et a un intérêt digne de protection à son annulation ou à sa modification (let. c). Lorsque l'acte attaqué est un acte normatif, l'intérêt personnel requis peut être simplement virtuel; il suffit qu'il existe un minimum de vraisemblance que le recourant puisse se voir un jour appliquer les dispositions contestées (<ref-ruling> consid. 2.2 p. 289, 133 II 353 consid. 3.3. p. 358). Quant à l'intérêt digne de protection, il n'est pas nécessaire qu'il soit de nature juridique, un intérêt de fait étant suffisant (<ref-ruling> consid. 2.2 p. 290). S'agissant d'une association, elle est habilitée à recourir même si elle n'est pas directement touchée par l'acte entrepris. Il faut cependant qu'elle ait la personnalité juridique et que la défense des intérêts de ses membres figure parmi ses buts statutaires. Il faut en outre que la majorité de ses membres, ou du moins une grande partie de ceux-ci, soit personnellement touchée par l'acte attaqué (<ref-ruling> consid. 1.2.1 p. 30 et la jurisprudence citée).
2.2 2.2.1 C._ est domicilié dans le canton de Genève. Il indique être au bénéfice de prestations de l'assurance-chômage. Il est possible qu'il doive un jour bénéficier des mesures prévues par le « Programme d'emplois de solidarité sur le marché complémentaire de l'emploi » suivant les art. 45D ss de la loi en matière de chômage et, dès lors, qu'il puisse se voir appliquer le règlement d'exécution de cette loi. Il convient dès lors de lui reconnaître la qualité pour recourir.
2.2.2 Le SIT, le SSP/VPOD et UNIA sont des organisations syndicales constituées sous la forme d'associations au sens des <ref-law>. Comedia est un syndicat constitué sous forme de société coopérative. Comedia, le SSP/VPOD et UNIA sont des organisations nationales, organisées par régions, tandis que le SIT est un syndicat genevois. Selon leurs statuts, ces organisations ont pour but de défendre les intérêts de leurs membres (art. 2 des statuts de Comedia; art. 3 al. 1 let. b des statuts du SSP/VPOD; art. 3 et 4 des statuts d'UNIA; art. 1.4 et 1.5 des statuts du SIT). Pour autant, on ne saurait sans plus retenir que la majorité, ou du moins une partie importante, des membres de ces organisations, résidant à Genève, risque un jour de se retrouver au chômage et, de surcroît, d'être en situation de bénéficier des mesures d'emplois de solidarité instituées par la législation genevoise. Ainsi, s'agissant du nombre de membres dont les intérêts dignes de protection sont touchés au sein de l'association, la jurisprudence a nié la qualité pour recourir de la Fédération des travailleurs du commerce, des transports et de l'alimentation (FCTA) et de la Société des employés de commerce, section de Zurich, contre les heures d'ouverture des commerces en gare de Zurich, au motif que les mesures en cause ne touchaient directement qu'un petit nombre (183 sur 25000 respectivement 16000) de leurs membres; un intérêt digne de protection, qui pouvait résulter de ce que leurs membres pourraient tous une fois faire partie du personnel de vente n'a pas été retenu comme suffisant (<ref-ruling> consid. 2a/cc p. 377 sv.). Or, en l'espèce, la majorité des membres des organisations recourantes n'est a priori pas plus touchée que l'ensemble des salariés genevois. La question de la qualité pour recourir des syndicats précités peut toutefois demeurer ouverte, dans la mesure où le Tribunal fédéral doit de toute manière entrer en matière sur le recours en tant qu'il est formé par C._.
2.2.3 La CGAS est une association au sens des <ref-law>. Elle est l'organisation faîtière du mouvement syndical genevois. Elle a pour but la défense des intérêts des travailleuses et travailleurs et de ses organisations membres, notamment dans le domaine du marché de l'emploi et de la lutte contre le chômage (art. 2 let. f de ses statuts). Selon l'art. 3 de ses statuts, la CGAS agit notamment par la réponse à des procédures de consultation (let. d), par sa présence dans les commissions consultatives du Conseil d'Etat ou dans tout autre organe de concertation (let. e). En outre, la CGAS a des représentants au sein du Conseil de surveillance du marché de l'emploi (CSME). Comme on le verra, cette association, à l'instar des autres recourants, se plaint d'une violation de la liberté syndicale, d'une violation du droit d'être entendu avant l'adoption du règlement litigieux, ainsi que du non-respect par le Conseil d'Etat de la procédure de préavis prévue par l'art. 45G al. 2 de la loi cantonale. Il faut dès lors admettre que, pour ces griefs tout au moins, la CGAS a qualité pour recourir. Il n'est pas nécessaire de décider si elle a également qualité pour agir en ce qui concerne les autres griefs soulevés dans le mémoire de recours.
3. 3.1 Les recourants se plaignent d'une violation du principe de la séparation des pouvoirs. Selon eux, le règlement contreviendrait à la loi cantonale en matière de chômage aussi bien dans sa procédure d'adoption que dans son contenu. S'agissant de la procédure d'adoption, ils font tout d'abord valoir que le Conseil d'Etat a violé l'art. 53 de la loi en omettant la procédure de consultation prévue par cette disposition. Ils reprochent en outre au Conseil d'Etat de n'avoir pas respecté la procédure de préavis prévue par l'art. 45G al. 2 de la loi s'agissant des salaires perçus par les bénéficiaires des emplois de solidarité. A l'appui de ce dernier grief, les recourants invoquent, en plus du principe de la séparation des pouvoirs, le droit à la liberté syndicale garanti par l'art. 28 Cst.
Il convient d'examiner ensemble ces griefs, qui tous deux relèvent de la procédure d'adoption du règlement contesté.
3.2 L'art. 53 de la loi en matière de chômage, qui figurait dans la précédente version de la loi, prévoit ceci: « Le Conseil d'Etat consulte les partenaires sociaux avant l'adoption ou la modification des dispositions d'exécution de la présente loi ». Quant à l'art. 45G al. 2 de la loi, il prévoit que le Conseil d'Etat détermine des salaires minimaux sur préavis du Conseil de surveillance du marché de l'emploi (ci-après: CSME). Dans ses déterminations, le Conseil d'Etat admet avoir adopté le règlement modifié sans une consultation formelle des partenaires sociaux telle qu'elle est prévue à l'art. 53 de la loi. Il attribue cette omission au souci de l'exécutif d'organiser le plus rapidement possible la mise en oeuvre des emplois de solidarité dans l'intérêt des chômeurs et alors que le processus législatif avait été bloqué pendant de nombreux mois en raison de la procédure référendaire. En revanche, le Conseil d'Etat conteste le grief des recourants concernant la procédure de préavis prévue par l'art. 45G al. 2 de la loi. Selon lui, cette procédure a été respectée.
3.2 L'art. 53 de la loi en matière de chômage, qui figurait dans la précédente version de la loi, prévoit ceci: « Le Conseil d'Etat consulte les partenaires sociaux avant l'adoption ou la modification des dispositions d'exécution de la présente loi ». Quant à l'art. 45G al. 2 de la loi, il prévoit que le Conseil d'Etat détermine des salaires minimaux sur préavis du Conseil de surveillance du marché de l'emploi (ci-après: CSME). Dans ses déterminations, le Conseil d'Etat admet avoir adopté le règlement modifié sans une consultation formelle des partenaires sociaux telle qu'elle est prévue à l'art. 53 de la loi. Il attribue cette omission au souci de l'exécutif d'organiser le plus rapidement possible la mise en oeuvre des emplois de solidarité dans l'intérêt des chômeurs et alors que le processus législatif avait été bloqué pendant de nombreux mois en raison de la procédure référendaire. En revanche, le Conseil d'Etat conteste le grief des recourants concernant la procédure de préavis prévue par l'art. 45G al. 2 de la loi. Selon lui, cette procédure a été respectée.
3.3 3.3.1 De manière générale, la Constitution fédérale ne confère pas aux citoyens le droit d'être entendus dans une procédure législative (<ref-ruling> consid. 2a p. 66). Une exception n'est admise que lorsque certaines personnes (destinataires dits « spéciaux ») sont touchées de façon sensiblement plus grave que le plus grand nombre des destinataires « ordinaires », par exemple lorsqu'un décret de portée générale ne touche qu'un très petit nombre de propriétaires (<ref-ruling> consid. 5 p. 149). Le Tribunal fédéral a par ailleurs admis que la liberté syndicale (art. 28 Cst.), si elle ne confère pas aux organisations syndicales de la fonction publique le droit de participer au processus législatif portant sur le statut du personnel, leur accorde néanmoins celui d'être entendues sous une forme appropriée en cas de modifications législatives ou réglementaires touchant de manière significative les conditions de travail de leurs membres (<ref-ruling> consid. 3 p. 120 ss).
En l'espèce, on ne saurait considérer les organisations recourantes ou le recourant C._ comme étant gravement et spécialement touchés par l'acte attaqué. D'autre part, celui-ci ne concerne pas le statut de la fonction publique, de sorte que l'art. 28 Cst. ne saurait être invoqué dans le présent contexte. Les recourants ne sauraient donc déduire un droit d'être entendus de la Constitution fédérale. C'est uniquement au regard du droit cantonal (art. 53 et 45G al. 2 de la loi en matière de chômage) qu'il convient d'examiner les griefs soulevés ici.
3.3.2 Le principe de la séparation des pouvoirs est garanti, au moins implicitement, par toutes les Constitutions cantonales et représente un droit constitutionnel dont peut se prévaloir le citoyen (<ref-ruling> consid. 3.1 p. 5 et les références). Ce principe garantit le respect des compétences établies par la Constitution. Il appartient en premier lieu au droit public cantonal de fixer les compétences des autorités (<ref-ruling> consid. 3.1 p. 5, 128 I 113 consid. 2c p. 116 et les références).
Dans le cas particulier, il ne fait pas de doute que le Conseil d'Etat était compétent pour édicter le règlement en cause (voir aussi infra consid. 4.2). L'argument selon lequel l'autorité exécutive n'aurait pas consulté préalablement les partenaires sociaux ou demandé un préavis au CSME n'a pas trait à la compétence du Conseil d'Etat d'adopter le règlement litigieux. Il s'agit bien plutôt de savoir si l'autorité compétente (le Conseil d'Etat) a respecté la procédure prévue à cet effet pour l'adoption du règlement. Un tel grief ne ressortit donc pas au principe de la séparation des pouvoirs, mais peut être soulevé en dénonçant une violation du principe général de l'interdiction de l'arbitraire inscrit à l'art. 9 Cst. (<ref-ruling>).
3.3.3 Ainsi qu'on l'a vu, la loi prévoit une double procédure de consultation, préalable et spéciale, en définissant le cercle des destinataires. Pour l'adoption ou la modification du règlement, le Conseil d'Etat est tenu de consulter les « partenaires sociaux » (art. 53), ce par quoi il faut entendre les organisations syndicales et patronales. Pour la détermination des salaires en faveur des bénéficiaires des emplois de solidarité, le Conseil d'Etat demande le préavis du CSME. Ce dernier est institué par les art. 12 ss de la loi genevoise sur le service de l'emploi et la location de services du 18 septembre 1992 (LSELS; RS GE J 2 05). Il a pour mission d'examiner les problèmes d'application relatifs à la politique générale du marché du travail. Font partie du Conseil cinq représentants de l'Etat, dont le conseiller d'Etat en charge du département compétent, qui le préside, ainsi que cinq représentants des employeurs et cinq représentants des travailleurs, nommés par le Conseil d'Etat, sur proposition de l'Union des associations patronales genevoises (UAPG) et de la (CGAS).
3.3.4 Il ressort d'un procès-verbal d'une séance du CSME du 12 octobre 2007 qu'à l'occasion de celle-ci, le conseiller d'Etat, chef du département de la solidarité et de l'emploi, a manifesté sa volonté, avant la votation populaire sur la loi en matière de chômage, de « démarrer les emplois de solidarité » au début de l'année 2008. Il a indiqué que le règlement d'exécution de la loi, en cours de préparation, serait présenté au CSME « pour validation ». Un représentant de la CGAS a alors répondu que, vu l'opposition des syndicats à la nouvelle loi, la CGAS n'entendait pas s'associer à des travaux qui anticiperaient la mise en oeuvre de celle-ci. En réponse à cette déclaration, le conseiller d'Etat a précisé que la loi ne serait évidemment pas appliquée avant la votation, mais qu'il convenait d'être prêt dans l'hypothèse où elle serait acceptée par le peuple.
3.3.5 Après que la loi eut été adoptée en votation populaire le 16 décembre 2007, le CSME a été convoqué à une séance pour le 18 janvier 2008. Les membres du Conseil on reçu une convocation datée du 14 janvier 2008 dans laquelle figurait l'ordre du jour. Le point 5 de celui-ci était le suivant :
« Emplois de solidarité sur le marché complémentaire de l'emploi - consultation CSME à teneur des art. 45E et 45F de la nouvelle loi cantonale en matière de chômage.»
Selon le procès-verbal de cette séance, le chef du département a rappelé que le préavis du CSME était prévu par la loi et qu'il portait sur la nature des emplois ainsi que sur les salaires. Il a indiqué que les emplois de solidarité seraient mis en place de manière progressive dès le 1er février 2008. Avec les programmes d'emploi-formation, ils remplaceraient les emplois temporaires cantonaux (contrats d'emplois temporaires conclus avec l'Etat en vue de l'ouverture d'un nouveau délai-cadre d'indemnisation par l'assurance-chômage fédérale). Le chef du département a distribué et commenté un projet relatif à la fixation des salaires mensuels, à savoir 3'000 fr. pour une fonction ne requérant aucune formation spécifique, 3'500 fr. pour une fonction occupée par un titulaire d'un CFC de la branche concernée ou d'un diplôme professionnel équivalent et 4'000 fr. pour une fonction spécialisée ou à responsabilités, requérant impérativement un CFC de la branche ou un diplôme professionnel équivalent. Les représentants de la CGAS ont regretté que le projet ne leur ait pas été remis à l'avance. Ils ont estimé qu'il n'était pas possible de se prononcer sur la question des salaires proposés sans une analyse technique préalable de la « compatibilité » avec les usages sectoriels. Ils ont exprimé l'avis que les trois niveaux de salaires proposés conduiraient à un dumping salarial et à une concurrence avec le marché principal de l'emploi. En conséquence, ils ont demandé la création d'un groupe de travail ad hoc chargé de l'examen de ces questions. Le chef du département a rappelé qu'il avait vainement proposé de traiter la question en octobre 2007. Finalement, le CSME a donné son aval à la mise en place d'un groupe technique paritaire. La CGAS et l'UAPG s'engageaient à désigner deux délégués jusqu'au 25 janvier 2008, pour tenir séance. La mission du groupe était « d'inventorier les questions d'application de la proposition de décision et de proposer des éventuelles adaptations fondées sur les critères d'équité et de simplicité administrative, dans un souci de prévention de dumping et de concurrence ». Dans l'intervalle, la proposition du Conseil d'Etat serait provisoirement applicable. Ce dispositif a été adopté avec une abstention.
Selon les indications fournies par le Conseil d'Etat dans sa réponse au recours, le « groupe technique » prévu a été convoqué par l'office cantonal de l'emploi, mais il n'a pas pu se réunir; en effet, les représentants patronaux ont refusé de participer à ce groupe de travail en raison du présent recours déposé entre temps par les organisations syndicales et la CGAS.
3.3.6 Il ressort de ce qui précède que les partenaires sociaux - au travers du CSME - ont été informés de l'intention du Conseil d'Etat de mettre rapidement sur pied les dispositions d'exécution de la loi modifiée en matière de chômage. Par la suite, le CSME a bien été invité à donner un préavis sur la question des salaires en faveur des bénéficiaires des emplois de solidarité. Ses membres ont eu l'occasion de faire valoir leurs objections. Ils ont donné leur accord à la mise en place d'un groupe de travail paritaire et accepté, provisoirement, les propositions salariales du Conseil d'Etat. Dans ces conditions, on peut admettre que la procédure de préavis prévue par l'art. 45G al. 2 de la loi a été respectée, même si le groupe de travail paritaire n'a pas été en mesure de se réunir pour formuler un préavis définitif. Un accord préalable du CSME n'est pas exigé par la loi et serait du reste dépourvu de force contraignante à l'égard de l'autorité (voir <ref-ruling> consid 3.1 p. 122). Le Conseil d'Etat ne pouvait, sous peine de paralyser le processus législatif et réglementaire, surseoir à la fixation des salaires selon l'art. 45G al. 2 de la loi.
Par ailleurs, la loi ne dit rien sur la manière dont le préavis requis doit être donné. Contrairement à ce que soutiennent les recourants, le fait que le Conseil d'Etat a soumis une grille de salaires au cours de la séance du CSME, et non pas préalablement à celle-ci, ne vide pas de sa substance la procédure de préavis prévue par la loi. L'essentiel, en effet, est que les membres du CSME ont eu la possibilité de donner leur avis. Au reste, la réserve d'un préavis définitif après l'entrée en vigueur du règlement, envisagée lors de la séance du 18 janvier 2008, témoigne d'une certaine continuité dans la consultation des partenaires sociaux et donc d'une flexibilité permettant au besoin d'adapter après coup le montant des salaires en fonction des recommandations éventuelles du CSME.
Le grief tiré d'une violation de l'art. 45G al. 2 de la loi n'est dès lors pas fondé.
3.3.7 En ce qui concerne la procédure de consultation prévue par l'art. 53 de la loi elle n'a pas été observée, ce qui n'est pas contesté. Le Conseil d'Etat, en effet, était tenu de soumettre pour consultation au CSME, voire de manière plus générale aux organisations syndicales et patronales, le projet de règlement (modifié) dans son ensemble. Cette procédure préalable n'est pas laissée à la discrétion du Conseil d'Etat, mais elle est obligatoire en vertu de la loi. Elle vise à améliorer l'acte en augmentant les connaissances de l'autorité. Elle permet de s'assurer que l'acte, une fois en vigueur, ne rencontrera pas de trop grandes difficultés dans son application. Elle favorise aussi une meilleure acceptation de celui-ci par les partenaires sociaux (voir, à propos de la procédure de consultation prévue par l'art. 147 Cst., JEAN-FRANÇOIS AUBERT/PASCAL MAHON, Petit commentaire de la Constitution fédérale de la Confédération suisse du 18 avril 1999, Zurich/Bâle/Genève 2003, note 3 ad art. 147 Cst., p. 1146). Il ne s'agit pas d'une simple prescription d'ordre. Le fait que le législateur cantonal a prévu une consultation spéciale des partenaires sociaux souligne l'importance qu'il y attache. La procédure de modification du règlement est donc entachée formellement d'une irrégularité.
3.3.8 Se pose dès lors la question de savoir quelles en sont les conséquences.
Des irrégularités formelles dans le déroulement d'un objet traité par un parlement ou une autorité exécutive ne peuvent totalement être évitées. Sauf exception, elles ne sauraient, pour des raisons tirées de la sécurité du droit, remettre en cause la validité de l'acte. Cependant, les arrêtés cantonaux (lois, règlements) peuvent être affectés de vices graves dans leur procédure d'adoption. De tels vices peuvent entraîner l'annulation de l'acte en cause, lorsqu'ils sont invoqués dans les délais en faisant usage d'un moyen de droit disponible (voir <ref-ruling>).
En l'espèce, le vice n'apparaît pas si grave qu'il doive conduire à l'annulation du règlement dans son ensemble. Cette sanction serait disproportionnée au regard des circonstances. Le règlement n'a pas été adopté à l'insu des partenaires sociaux, qui ont eu la possibilité de se faire entendre dès le mois d'octobre 2007 déjà. En outre, une consultation des partenaires sociaux - par le biais du CSME - a eu lieu sur un point important et controversé du règlement, intéressant de surcroît plus particulièrement ces derniers, à savoir les modalités d'indemnisation des bénéficiaires des emplois de solidarité. En octobre 2007, l'attention des partenaires sociaux a été attirée sur le fait que le projet en cours leur serait présenté pour «validation », ce qui faisait incontestablement référence à la procédure de consultation exigée par l'art. 53 de la loi. S'ils estimaient que cette procédure devait encore être mise en oeuvre, ils pouvaient le faire savoir au Conseil d'Etat à l'occasion de la séance du 18 janvier 2008. On peut ainsi considérer qu'ils ont implicitement renoncé à une détermination sur l'ensemble des modifications du règlement, pour concentrer leur intérêt sur les questions salariales.
3.4 En conséquence, les conclusions des recourants tendant à l'annulation du règlement en raison de vices dans sa procédure d'adoption sont mal fondées.
4. 4.1 Invoquant une violation du principe de la séparation des pouvoirs, les recourants font valoir que l'art. 43 du règlement est contraire au contenu matériel de l'art. 45G al. 2 de la loi en matière de chômage. Cette disposition légale prévoit que le Conseil d'Etat « détermine les salaires minimaux ». Or, l'art. 43 du règlement fixe le salaire mensuel brut de l'emploi de solidarité, selon les qualifications du travailleur, à 3'000 fr., 3'500 fr. et 4'000 fr. Selon les recourants, ces montants sont en réalité des salaires obligatoires et non des salaires plancher comme l'exige la loi.
4.2 L'art. 130 de la Constitution genevoise (Cst. gen.) consacre expressément le principe de la séparation des pouvoirs. Si le pouvoir législatif est exercé par le Grand Conseil (art. 70 Cst. gen.), le pouvoir exécutif et l'administration générale du canton sont confiés au Conseil d'Etat (art. 101 Cst. gen.). Selon l'art. 116 Cst. gen., le Conseil d'Etat a pour tâche de promulguer les lois; il est chargé de leur exécution et prend à cet effet les règlements et arrêtés nécessaires. Il ne peut ainsi disposer qu'intra legem et non praeter legem: ses règlements peuvent établir des règles complémentaires de procédure, préciser et détailler certaines dispositions de la loi et, éventuellement, combler de véritables lacunes (<ref-ruling>40 consid. 5.1 p. 149, 129 V 95 consid. 2.1 p. 97, 124 I 127 consid. 3b p. 132 et les références).
4.3 Le projet de loi en matière de chômage présenté par le Conseil d'Etat le 26 septembre 2006 prévoyait ceci à son art. 45G al. 1: « Le département fixe le montant et les modalités de la rémunération accordée aux bénéficiaires du programme ». A son alinéa 3, il précisait que les relations contractuelles entre les bénéficiaires et les institutions étaient régies pour le surplus par le contrat de travail signé par ces derniers et, à titre supplétif, par les dispositions du titre dixième du Code des obligations. Au cours de la procédure de consultation, certaines institutions (Caritas, le Centre social protestant) ont fait valoir que le projet soulevait sur ce point des difficultés, car lesdites institutions pouvaient être amenées à conclure des contrats pour des emplois de solidarité avec des salaires inférieurs à ceux fixés dans leur propre statut du personnel. La Commission de l'économie chargée d'étudier le projet a alors proposé de modifier la disposition en cause en prévoyant que le Conseil d'Etat fixerait des salaires minimaux après consultation du CSME. Cette proposition a été retenue dans la version définitive de l'art. 45G al. 2 de la loi.
4.4 En déléguant au Conseil d'Etat le pouvoir de fixer des salaires minimaux, le législateur cantonal n'exige pas forcément que l'employeur accorde aux bénéficiaires - ou à certains d'entre eux - des salaires plus élevés que les salaires minimums prévus. Les motifs qui ont conduit la Commission de l'économie à modifier le projet initial donnent à penser que le législateur a voulu confier au Conseil d'Etat le pouvoir de fixer lui-même dans son règlement d'exécution des normes minimales afin d'éviter que la fixation des salaires soit laissée, comme prévu initialement, à l'appréciation du département. La consultation du CSME - qui n'était pas prévue dans le projet initial - devait également permettre au Conseil d'Etat de prendre en compte les préoccupations des partenaires sociaux en matière salariale. Le terme « minimaux » peut être compris en ce sens que le Conseil d'Etat est tenu de fixer des montants qui représentent un salaire garanti pour les intéressés. Il ne signifie pas nécessairement que les salaires doivent être individualisés ou déterminés de cas en cas en fonction des normes salariales pratiquées par l'institution partenaire. Au demeurant, en fixant trois paliers de rémunération, le Conseil d'Etat a adopté un échelonnement qui permet déjà, en la relativisant, une interprétation nuancée de la notion de salaires minimaux.
4.5 Dès lors, ici également, le grief tiré d'une violation de l'art. 45G al. 2 de la loi est mal fondé.
5. 5.1 Les recourants se prévalent encore à un autre titre du principe de la séparation des pouvoirs. Ils font valoir que le règlement d'exécution, à ses art. 43 et 44, prévoit un système différent de celui prévu à l'art. 45G de la loi. Selon l'art. 44 al. 1 du règlement d'exécution, la différence entre les salaires prévus et le salaire minimal résultant de la législation sociale (art. 45G al. 1 de la loi) fait l'objet d'une allocation complémentaire. L'art. 44 al. 2 du règlement d'exécution prévoit que cette allocation complémentaire n'est pas assimilée à un salaire et ne donne pas lieu à prélèvement de cotisations sociales. Selon les recourants, cette réglementation suppose donc que l'allocation complémentaire est une prestation sociale versée par l'Etat. Ce système serait donc contraire à l'art. 45G al. 1 de la loi qui exige que le salaire versé par l'institution partenaire (employeuse) doit respecter les normes de la législation sociale. Il contreviendrait également à l'art. 45G al. 4 de la loi, selon lequel le contrat de travail donne lieu au prélèvement des cotisations sociale usuelles : de l'avis des recourants, cette disposition de la loi exclut qu'une partie du salaire soit versée sous forme d'allocations de l'Etat non soumises aux cotisations sociales.
5.2 L'art. 45G al. 1 de la loi prévoit que les bénéficiaires perçoivent de la part des institutions partenaires un salaire dont le montant est au moins équivalent aux normes prévues par la loi sur les prestations cantonales accordées aux chômeurs en fin de droit ou par les normes de l'aide sociale. Son but est d'accorder une rémunération qui soit au moins équivalente aux prestations de l'aide sociale, sous peine de décourager les bénéficiaires potentiels de prendre un emploi de solidarité (Rapport de la Commission de l'économie chargée d'étudier le projet de loi du Conseil d'Etat modifiant la loi en matière de chômage). L'exigence posée à l'art. 45G al. 1 de la loi ne précise toutefois pas ce qu'il faut entendre par « normes ». Cette notion est sujette à interprétation. L'aide sociale et les allocations accordées aux chômeurs en fin de droit dépendent en effet pour une part de la situation individuelle des bénéficiaires, en particulier de leur situation de famille et des dépenses à leur charge. Cette composante individuelle est en revanche étrangère à la notion de salaire, qui représente par définition la contrepartie pour un travail fourni. Le Conseil d'Etat se devait donc d'adopter une solution qui se concilie avec l'exigence d'une rémunération minimale et les paramètres variables de l'aide sociale.
5.3 Selon la loi sur les prestations cantonales accordées aux chômeurs en fin de droit, du 18 novembre 1994 (LRMCAS; RS GE J 2 25), ces prestations sont allouées aux personnes qui sont au chômage, qui ont épuisé leur droit aux prestations de l'assurance-chômage (régime fédéral et cantonal; art. 1 LRMCAS/GE) et dont le revenu annuel déterminant n'atteint pas le revenu minimum cantonal d'aide sociale (art. 4 LRMCAS). Le revenu minimum cantonal d'aide sociale garanti aux chômeurs en fin de droit est de 15'734 fr. depuis le 1er janvier 2007 (art. 3 LRMCAS en corrélation avec le règlement relatif à l'indexation des prestations cantonales accordées aux chômeurs en fin de droit, du 29 novembre 2006 (RIPCFD; RS GE J 2 25.01). Il peut être complété, dans les limites du barême de l'assistance publique, par des allocations ponctuelles destinées à la prise en charge de certains frais, tels que les frais de vêtements ou de maladie. Conformément à l'art. 3 al. 2 LRMCAS, le montant minimum (15'734 fr.) est multiplié par:
a) 1,46 s'il s'agit de deux personnes;
b) 1,88 s'il s'agit de trois personnes;
c) 2,20 s'il s'agit de quatre personnes;
d) 2,50 s'il s'agit de cinq personnes;
e) 0,30 par personne supplémentaire au-delà de cinq personnes.
Le salaire minimum de 3'000 fr. (36'000 fr. par année) prévu à l'art. 43 du règlement est donc légèrement supérieur au revenu minimum cantonal d'aide sociale pour quatre personnes selon l'art. 3 al. 2 LRMCAS. On ne peut donc pas dire que le Conseil d'Etat ait outrepassé ses pouvoirs en fixant un plancher qui est plus proche des maxima que des minima à considérer au regard de la LRMCAS. Le montant minimum garanti pour quatre personnes couvre une très large partie des bénéficiaires potentiels. Il n'y aurait aucun sens à fixer des salaires minimums en partant de situations personnelles plus ou moins exceptionnelles. A ce propos d'ailleurs, le Conseil d'Etat indique dans sa réponse qu'aucun emploi de solidarité mis en place avec les institutions partenaires n'a jusqu'à présent donné lieu au paiement d'un complément prévu par l'art. 44 du règlement. Le seul fait que le Conseil d'Etat a prévu dans cette disposition le versement d'une allocation complémentaire, pour tenir compte de situations individuelles tout à fait particulières, ne permet pas de conclure qu'il a restreint de manière inadmissible la portée de la loi. Au demeurant, les recourants ne précisent pas quel est le montant minimum qui devrait être garanti selon les normes de l'aide sociale. Ici également le grief soulevé se révèle mal fondé.
6. 6.1 Les recourants font enfin valoir que les salaires fixés par le Conseil d'Etat à l'art. 43 du règlement pourraient être plus bas que ceux prévus par les conventions collectives de travail. Or, les salaires minimums prévus par les conventions collectives sont impératifs dans la mesure où l'employeur et le travailleur sont liés par une telle convention. De plus, lorsqu'une convention collective a fait l'objet d'un arrêté d'extension, les dispositions normatives de la convention collective, dont font partie les salaires minimaux, s'appliquent également aux employeurs et travailleurs auxquels la convention est étendue. De même, les salaires minimaux prévus par des contrats -types au sens de l'<ref-law> sont également impératifs. Aussi bien l'art. 43 du règlement devrait-il être annulé pour violation du principe de la primauté du droit fédéral (art. 49 al. 1 Cst.).
6.2 L'art. 49 al. 1 Cst. fait obstacle à l'adoption ou à l'application de règles cantonales qui éludent des prescriptions de droit fédéral ou qui en contredisent le sens ou l'esprit, notamment par leur but ou par les moyens qu'elles mettent en oeuvre, ou qui empiètent sur des matières que le législateur fédéral a réglementées de façon exhaustive. Le principe de la force dérogatoire du droit fédéral peut être invoqué en tant que droit constitutionnel individuel. Le Tribunal fédéral examine avec un plein pouvoir d'examen si la norme de droit cantonal est conforme au droit fédéral (<ref-ruling> consid. 2.1 p. 128, 133 I 286 consid. 3.1 p. 290 et les références).
6.2 L'art. 49 al. 1 Cst. fait obstacle à l'adoption ou à l'application de règles cantonales qui éludent des prescriptions de droit fédéral ou qui en contredisent le sens ou l'esprit, notamment par leur but ou par les moyens qu'elles mettent en oeuvre, ou qui empiètent sur des matières que le législateur fédéral a réglementées de façon exhaustive. Le principe de la force dérogatoire du droit fédéral peut être invoqué en tant que droit constitutionnel individuel. Le Tribunal fédéral examine avec un plein pouvoir d'examen si la norme de droit cantonal est conforme au droit fédéral (<ref-ruling> consid. 2.1 p. 128, 133 I 286 consid. 3.1 p. 290 et les références).
6.3 6.3.1 Il découle de l'<ref-law> que les clauses relatives notamment au contenu des contrats individuels de travail n'ont en principe d'effet direct et impératif qu'envers des employeurs et travailleurs qu'elles lient. De telles clauses s'appliquent automatiquement, sans incorporation dans le contrat de travail, et les parties ne peuvent y déroger contractuellement au détriment du salarié (cf. GABRIEL AUBERT, Commentaire romand no 3 sv. ad <ref-law>). Ces effets supposent que les deux parties soient liées. Tel est le cas si l'employeur est personnellement partie à la convention, si l'employeur et le travailleur sont membres d'une association contractante (<ref-law>), ou encore si l'employeur et le travailleur ont fait une déclaration de soumission volontaire au sens de l'<ref-law> et ont obtenu le consentement des parties (cf. <ref-ruling> consid. 3a p. 131; arrêt 4C.276/2004 du 12 octobre 2004).
6.3.2 La décision d'extension permet l'application d'une convention collective de travail aux employeurs et aux travailleurs qui appartiennent à la branche économique ou à la profession visée et ne sont pas liés par cette convention (cf. art. 1 al. 1 de la loi fédérale du 28 septembre 1956 permettant d'étendre le champ d'application de la convention collective du travail [LECCT; RS 221.215.311]). Pour savoir si une entreprise appartient à la branche économique ou à la profession visée et entre, de ce fait, dans le champ d'application de la convention étendue, il faut examiner de manière concrète l'activité généralement déployée par l'entreprise en cause (arrêt 4P.49/2006 du 24 avril 2006, consid. 3.3). Seule doit être prise en considération, dans le cadre de cet examen, l'activité généralement exercée par l'employeur en question (arrêt 4C.409/1995 du 15 mai 1996, consid. 2b). Les entreprises visées par la déclaration d'extension doivent offrir des biens ou des services de même nature que les entreprises qui sont soumises contractuellement à la convention; il doit exister un rapport de concurrence directe entre ces entreprises (arrêts 4C.45/2002 du 11 juillet 2002 consid. 2.1.2 et 4C.46/1995 du 11 octobre 1995 consid. 3a).
6.3.3 Enfin, conformément à l'<ref-law>, si, au sein d'une branche économique ou d'une profession, les salaires usuels dans la localité, la branche ou la profession font l'objet d'une sous-enchère abusive et répétée et qu'il n'existe pas de convention collective de travail contenant des dispositions relatives aux salaires minimaux pouvant être étendue, l'autorité compétente peut édicter, sur proposition de la commission tripartite visée à l'art. 360b, un contrat-type de travail d'une durée limitée prévoyant des salaires minimaux différenciés selon les régions et, le cas échéant, selon les localités, dans le but de combattre ou de prévenir les abus.
6.4 Comme cela ressort de l'art. 45E de la loi, les emplois de solidarité sont créés sur le marché complémentaire de l'emploi. Ils doivent viser à l'insertion professionnelle des demandeurs d'emploi. Dans le choix des activités retenues, le département veille à éviter toute concurrence avec des entreprises commerciales genevoises, en particulier celles régies par des conventions collectives de travail. Les emplois proposés relèvent donc d'activités délaissées par le marché ordinaire de l'emploi. Leur mise en oeuvre requiert le concours de l'Etat par le biais de subventions. Le législateur genevois a voulu empêcher tout risque de dumping salarial en évitant la création d'un rapport de concurrence directe entre les institutions partenaires et l'économie dite « primaire ». L'éventualité que ces institutions entrent dans le même domaine d'activité que des entreprises englobées dans une décision d'extension est donc tout à fait théorique.
6.5 Par ailleurs, l'art. 45D al. 3 de la loi exclut de façon explicite un droit pour le chômeur d'obtenir une mesure déterminée, par exemple un emploi dans l'institution de son choix. L'Etat choisit librement les institutions partenaires. Le droit fédéral ne l'oblige pas à choisir une institution partenaire qui, par hypothèse, serait soumise à une convention collective. En outre, comme le relève le Conseil d'Etat dans sa réponse, les particularités liées aux emplois de solidarité, qui présentent indiscutablement une composante de formation, peuvent justifier de soumettre à un régime spécial les emplois de solidarité en ce qui concerne le montant des salaires. Dans cette perspective, il est loisible aux parties contractantes de modifier le champ d'application personnel d'une convention collective de travail pour tenir compte de ces particularités.
6.6 Intrinsèquement, les dispositions en matière de salaire adoptées par le Conseil d'Etat n'apparaissent donc pas contraires au droit fédéral. Même si on ne peut d'emblée exclure, dans un cas concret, que le salaire fixé par le règlement soit inférieur au salaire minimum prévu dans une convention collective (ou un contrat-type), le grief d'inconstitutionnalité ne peut pas être retenu. En effet, si une norme semble compatible avec le droit fédéral, au regard des circonstances ordinaires que le législateur devait considérer, le juge ne l'annulera pas pour le seul motif qu'on ne peut exclure absolument l'éventualité de son application contraire au droit à des cas particuliers. Il ne le fera que si la perspective d'un contrôle concret ultérieur n'offre pas de garantie suffisante au destinataire de la norme litigieuse (cf. arrêts 2C_218/2007 du 9 octobre 2007 consid. 3, 2C_71/2007 du 9 octobre 2007 consid. 2.6; cf., sous l'empire de l'OJ, <ref-ruling> consid. 3.2 p. 15, 128 I 327 consid. 3.1 p. 334 sv. et les arrêts cités). Or, tel n'est pas le cas en l'espèce, dans la mesure où le bénéficiaire d'un emploi de solidarité a toujours la possibilité de saisir le juge civil dans l'hypothèse où la rémunération perçue ne serait pas conforme à une convention collective.
6.7 Le grief des recourants tiré de la primauté du droit fédéral doit donc aussi être rejeté.
7. Les considérants qui précèdent conduisent au rejet du recours en matière de droit public dans la mesure où il est recevable. Succombant, les recourants supporteront les frais de justice (<ref-law>). Le canton de Genève, contrairement à ses conclusions, n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Un émolument judiciaire de 5'000 fr. est mis à la charge des recourants.
3. Le présent arrêt est communiqué aux parties, au Conseil d'Etat de la République et canton de Genève et au Secrétariat d'Etat à l'économie.
Lucerne, le 3 octobre 2008
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral