Faits:
A. La Société X._, qui a son siège à Martigny, occupe depuis plusieurs années des agents salariés dans toute la Suisse, notamment dans le canton de Berne. Ces employés étaient affiliés à la Caisse interprofessionnelle valaisanne d'allocations familiales (CIVAF) jusqu'au 31 décembre 2005. Le 6 décembre 2005, La Société X._ a demandé son affiliation à la Caisse de compensation du canton de Berne (CCB), à partir du 1er janvier 2006, pour tous ses agents exerçant leur activité dans le canton de Berne. Par décision du 13 décembre 2007, la CCB a rendu une décision d'affiliation pour les années 2002 à 2005 (soit dans les limites du délai quinquennal de prescription) pour les collaborateurs de la Société X._ employés dans le canton de Berne. Les cotisations correspondant aux années en question ont été fixées en même temps à 59'925 fr. 25.
B. La Société X._ a recouru contre cette décision devant le Tribunal administratif du canton de Berne. Il a déposé une attestation de la CIVAF, selon laquelle les agents de la Société X._ en Suisse avaient été déclarés à cette caisse pour les années 2001 à 2005; celle-ci avait versé aux ayants droit les allocations familiales selon le droit du canton du Valais, bien qu'ils fussent domiciliés dans d'autres cantons.
Statuant le 9 février 2009, le Tribunal administratif a rejeté le recours.
C. La Société X._ a formé un recours en matière de droit public dans lequel il a conclu à l'annulation de ce jugement et de la décision administrative précédente.
Le Tribunal administratif s'est déterminé sur le recours. La CCB en a fait de même et elle a conclu à son rejet.

Considérant en droit:
1. Le recours est interjeté par une partie directement touchée par la décision attaquée et qui a un intérêt digne de protection à son annulation ou à sa modification (cf. <ref-law>). Il est dirigé contre une décision rendue dans une cause de droit public (cf. <ref-law>) en dernière instance cantonale par un tribunal supérieur (cf. art. 86 al. 1 let. d et al. 2 LTF). Il a de plus été déposé en temps utile (<ref-law>) et aucune des exceptions énumérées à l'<ref-law> n'est réalisée.
2. La situation de fait et de droit à l'origine du présent litige est antérieure à l'entrée en vigueur, le 1er janvier 2009, de la loi fédérale du 24 mars 2006 sur les allocations familiales (Loi sur les allocations familiales [LAFam; RS 836.2]). Auparavant, la Confédération n'avait usé de sa compétence législative en matière d'allocations familiales (art. 116 Cst.) que pour les salariés agricoles et les petits paysans (cf. la loi fédérale du 20 juin 1952 sur les allocations familiales dans l'agriculture [LFA; RS 836.1]). Le présent recours doit donc être tranché au regard du droit cantonal. Il s'agit en l'occurrence la loi cantonale bernoise sur les allocations pour enfants aux salariés (LAE) du 5 mars 1961 et de l'ordonnance d'exécution de cette loi du 28 avril 1961 (OAPE).
3. Selon l'<ref-law>, le recours ne peut être formé que pour violation du droit fédéral, y compris les droits constitutionnels (<ref-law>), mais non pour violation du droit cantonal en tant que tel. Il est néanmoins possible de faire valoir que la mauvaise application ou la mise en oeuvre des dispositions cantonales consacrent une violation du droit fédéral, comme la garantie des droits constitutionnels (<ref-ruling> consid. 2.3 p. 466). Le Tribunal fédéral n'examine cependant de tels moyens que s'ils sont formulés conformément aux exigences de motivation qualifiées prévues à l'<ref-law>.
4. 4.1 Sous le titre «Employeurs assujettis», l'art. 3 LAE prévoit ceci:
«Sont soumis à la présente loi tous les employeurs qui ont leur domicile, le siège de leur entreprise, une succursale, un établissement ou un chantier dans le canton de Berne et qui occupent des salariés en Suisse, à la condition que ces derniers ne soient pas au bénéfice de mêmes allocations versées par un autre canton et sous réserve des exceptions statuées aux articles ci-après».
Les exceptions auxquelles il est fait référence sont prévues aux art. 4 LAE (représentations officielles des États étrangers, services de l'administration fédérale, exploitations agricoles), 5 LAE (entreprises avec réglementation des salaires) et 6 LAE (les employeurs parties à une convention collective dite d'entreprise stipulant des allocations pour enfants sous les mêmes conditions et aux mêmes taux que ceux mentionnés dans la loi). Ces exceptions sont sans pertinence pour l'issue du litige en l'espèce.
4.2 L'art. 11 LAE prévoit que tous les employeurs soumis à cotisations qui ne s'affilieront pas à une caisse privée reconnue d'allocations familiales seront rattachés à la caisse cantonale d'allocations familiales dès le début de leur obligation de verser des cotisations (al. 1). L'employeur tenu à cotisations doit s'annoncer dans un délai de trois mois à compter du début de son assujettissement, à la caisse d'allocations familiales de son choix (al. 2).
4.3 Quant à l'art. 3 OAPE, il a la teneur suivante:
1«Les employeurs mentionnés à l'art. 3 de la loi doivent, dans les trois mois suivant le début de leur obligation de cotiser, s'annoncer à l'office communal de compensation [teneur à partir du 27 mars 2002 : à l'agence AVS] de leur lieu de domicile ou du siège de leur entreprise et prouver, à l'intention de la Caisse cantonale d'allocations familiales:
a) qu'ils sont libérés de l'obligation d'adhérer à une caisse d'allocations familiales en vertu des art. 5 et 6 de la loi ou
b) qu'ils sont membres d'une caisse privée d'allocations familiales reconnue (art. 17 de la loi) ou
c) que leurs employés et ouvriers ont droit aux allocations familiales sur la base de la législation d'un autre canton.
2(...)
3Les employeurs qui ne pourront apporter la preuve précitée seront, en conformité avec l'art. 11 de la loi, affiliés à la Caisse cantonale d'allocations familiales.
4Les succursales et les branches de l'entreprise d'un employeur dont l'entreprise principale est affiliée à la caisse d'allocations familiales d'un autre canton peuvent, sur demande de l'employeur, être rattachées à cette caisse. [abrogé dès le 21 septembre 2005]
5(...)».
5. 5.1 Le Tribunal administratif retient que le recourant ne s'est pas annoncé à la CCB dans le délai de trois mois de l'art. 3 al. 1 OAPE. Partant, il n'a pas prouvé en temps utile que ses employés avaient droit aux allocations familiales en Valais. Il n'a pas davantage présenté une demande de rattachement à une caisse d'un autre canton au sens de l'art. 3 al. 4 OAPE. Dans ces conditions, une dispense de cotiser à la CCB ne pouvait en l'espèce pas être accordée a posteriori. Cela justifiait l'affiliation d'office (et rétroactive) du recourant au sens de l'art. 11 al. 1 LAE pour ce qui concerne ses collaborateurs actifs dans le canton de Berne.
5.2 Le recourant fait valoir que les premiers juges ont versé dans le formalisme excessif et l'arbitraire en l'obligeant à payer des cotisations rétroactives à la CCB alors que celle-ci n'aura pas d'allocations à verser aux intéressés. Selon lui, la double affiliation que lui impose le jugement cantonal est contraire aux principes généraux en matière de double assurance. Le recourant se prévaut également de l'interdiction de l'abus de droit et du principe de la bonne foi.
6. On peut relever préliminairement que, même si les contributions de droit cantonal aux caisses d'allocations familiales présentent un caractère fiscal, elles ne peuvent être assimilées à des impôts généraux sur le revenu et la fortune. Elles peuvent toutefois constituer des impôts d'affectation (cf. André Zünd, Familièrement und Familienausgleichskassen der privaten Wirtschaft, Zurich et Saint-Gall 1955, p. 164 ss, plus spécialement p. 166). Le point de savoir si de tels impôts sont visés par l'interdiction de la double imposition intercantonale (art. 46 al. 2 de la Constitution de 1874; art. 127 al. 3 de la Constitution de 1999) a été laissé indécis par le Tribunal fédéral dans un arrêt du 30 octobre 1997 (arrêt 2P.210/1996 in SJ 1998 p. 473 consid. 7). En l'espèce, la question peut également demeurer ouverte, du moment que le recourant ne se prévaut pas de la garantie de l'art. 127 al. 3 Cst.
7. 7.1 D'après la jurisprudence, il y a formalisme excessif, constitutif d'un déni de justice formel prohibé par l'art. 29 al. 1 Cst., lorsque la stricte application des règles de procédure ne se justifie par aucun intérêt digne de protection, devient une fin en soi et complique de manière insoutenable la réalisation du droit matériel, ou entrave de manière inadmissible l'accès aux tribunaux. L'excès de formalisme peut résider soit dans la règle de comportement imposée au justiciable par le droit cantonal, soit dans la sanction qui lui est attachée (<ref-ruling> consid. 2.4.2 p. 248; <ref-ruling> consid. 5.4.1 p. 183; <ref-ruling> consid. 2a p. 142 et les références citées).
7.2 Comme on l'a vu, les contributions aux allocations familiales peuvent être considérées comme des impôts d'affectation. Dû indépendamment de l'usage ou de l'avantage obtenu individuellement par le contribuable ou de la dépense que celui-ci a provoquée, un tel impôt se satisfait d'un lien relativement abstrait et lâche entre les dépenses financées par ces contributions et les personnes qui sont assujetties (<ref-ruling> consid. 5.1 p. 354; <ref-ruling> consid. 4b in fine p. 310).
7.3 En l'espèce, il est établi que le recourant a déclaré à la CIVAF les salaires de tous ses agents occupés en Suisse (et donc aussi ceux qui ont travaillé dans le canton de Berne durant la période en cause). Il est également constant que cette caisse a versé pour les ayants droit concernés les allocations familiales leur revenant. Pour la période litigieuse, il n'y a donc aucun lien, même relativement lâche, entre l'assujettissement rétroactif à la CCB et le besoin de financement de ces allocations. Par ailleurs, l'art. 3 LAE exempte de l'affiliation à la loi, en particulier, les employeurs qui ont une succursale dans le canton de Berne, si les salariés concernés ont les mêmes allocations versées par un autre canton. Il n'est pas contesté que cette dernière condition est réalisée en l'espèce. D'après cette réglementation cantonale, le recourant n'était donc pas tenu de s'affilier à la CCB. Le fait qu'il ne s'est pas annoncé dans un certain délai à ladite caisse n'a pas de rapport direct avec les conditions matérielles de l'affiliation. L'exigence d'une annonce dans un délai de trois mois apparaît bien plutôt comme une prescription de procédure visant à garantir que l'ensemble des salariés occupés dans le canton de Berne soit au bénéfice d'un régime cantonal d'allocations familiales. Le non-respect de ce délai peut certes entraîner une affiliation rétroactive quand l'employeur ne parvient pas à rapporter la preuve que ses salariés bénéficient des mêmes allocations versées dans un autre canton ou lorsqu'il subsiste des doutes à ce sujet. En revanche, lorsque le fait est indiscutable, comme en l'espèce, on ne voit pas quel intérêt digne de protection justifierait une affiliation rétroactive impliquant la perception dans deux cantons de contributions sur des mêmes salaires.
Dans de telles conditions, on ne perçoit aucun motif suffisamment pertinent pour obliger le recourant à se soumettre à une double affiliation pour la seule raison qu'il ne s'est pas annoncé à la caisse dans le délai de trois mois prévu par l'art. 3 al. 1 OAPE. L'affiliation rétroactive du recourant apparaît plus comme une mesure destinée à sanctionner le non-respect de ce délai que comme une mesure propre à garantir le droit des bénéficiaires aux allocations. Pareille sanction procède en l'espèce d'un formalisme excessif dans l'application du droit cantonal. Il existe au demeurant d'autres mesures susceptibles de sanctionner des contraventions par l'employeur aux prescriptions. Ainsi un contrevenant est passible de l'amende prévue à l'art. 32 al. 1 LAE (de 500 à 2000 fr.) en cas d'infraction aux prescriptions d'ordre et de contrôle; il est en outre soumis à une responsabilité analogue à l'<ref-law> pour le dommage causé à la caisse (art. 32 al. 2 LAE).
8. Dans sa réponse au recours, la CCB indique, sans autres précisions, qu'elle versera rétroactivement aux salariés concernés les allocations pour enfants pour autant que toutes les conditions en soient remplies.
Ce versement aurait toutefois pour conséquence que les ayants droit bénéficieraient d'une double allocation. S'il est vrai que la perception d'une double allocation à un même ayant droit n'est pas contraire à la Constitution (<ref-ruling> consid. 5.1 p. 275), il n'en reste pas moins que les anciens régimes cantonaux d'allocations familiales avaient aménagé des critères pour l'attribution du droit en cas de concours, afin précisément d'éviter une double perception de la prestation (voir Pascal Mahon, Les allocations familiales, in Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, 2ème éd., p. 1970 sv. no 50 ss). Dans l'<ref-ruling>, précité, le Tribunal fédéral a jugé qu'il était contraire à la Constitution de considérer le mari comme allocataire prioritaire. Il a préconisé l'application par analogie des règles de conflit figurant aux art. 73 et 76 du règlement (CEE) n° 1408/71 et valables pour les relations entre la Suisse et l'Union européenne sur la base de l'accord de libre circulation des personnes (ALCP). Sur le plan de la législation fédérale, l'<ref-law> pose le principe de l'interdiction du cumul et l'art. 7 fixe un ordre de priorité en cas de concours de droits. L'<ref-law> (dans sa version en vigueur depuis le 1er janvier 2009) déclare applicables par analogie ces deux dispositions. Auparavant, la LFA contenait, à son art. 9 al. 3 à 5 et à son art. 10, des règles sur le concours de prestations et sur l'interdiction du cumul. Il est donc évident que tant les anciennes réglementations cantonales que la législation fédérale avaient et ont pour objectif qu'un même enfant ne donne droit qu'à une allocation du même genre. L'argument de la caisse tiré du versement rétroactif des prestations, qui va à l'encontre de cet objectif, ne constitue en soi pas une justification pertinente d'une affiliation rétroactive du recourant.
9. De ce qui précède, il résulte que le recours est bien fondé.
La CCB, dont l'intérêt patrimonial est en cause, doit supporter les frais judiciaires (art. 66 al. 4 a contrario LTF). Aucune indemnité de dépens n'est due au recourant, qui agit par lui-même (<ref-ruling> consid. 5b p. 519; <ref-ruling> consid. 7 p. 82).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et le jugement du Tribunal administratif du canton de Berne du 9 février 2009, ainsi que la décision de la Caisse de compensation du canton de Berne du 13 décembre 2007, sont annulés.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de la Caisse de compensation du canton de Berne.
3. La cause est renvoyée au Tribunal administratif du canton de Berne pour nouvelle décision sur les frais et dépens de l'instance cantonale.
4. Le présent arrêt est communiqué aux parties, au Tribunal administratif du canton de Berne, Cour des affaires de langue française, et à l'Office fédéral des assurances sociales.
Lucerne, le 15 janvier 2010
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Ursprung von Zwehl