Faits:
A. Me G._, avocat à N._, a été nommé avocat d'office pour défendre les intérêts de P._ dans une procédure administrative opposant celui-ci à la Caisse nationale suisse d'assurance en cas d'accidents (CNA), division Assurance militaire. Le 31 mai 2006, l'assureur a fixé à 900 fr. l'indemnité de l'avocat d'office, soit 750 fr. au titre des honoraires (350 fr. pour la procédure de préavis-décision et 400 fr. pour la procédure d'opposition), ainsi que 150 fr. de débours et frais.
B. G._ a recouru contre cette décision devant le Tribunal administratif de la République et canton de Neuchâtel en concluant au paiement d'une indemnité de 3'333 fr. 45 au titre des honoraires, des débours et de taxe à la valeur ajoutée, sous déduction de la somme de 900 fr. déjà versée.
Par lettre du 26 juin 2006, le Tribunal administratif a invité l'avocat à verser dans un délai de dix jours une avance de frais de 770 fr. en garantie des frais de procédure présumés. Par lettre du lendemain, l'avocat a contesté son obligation de verser une avance de frais, en invoquant le principe de la gratuité de la procédure en matière d'assurances sociales. Le 5 juillet 2006, le président du Tribunal administratif a répondu que la gratuité de la procédure ne s'appliquait qu'aux litiges en matière d'assurances sociales opposant un assuré à un assureur, voire des assureurs entre eux. En revanche, selon la jurisprudence neuchâteloise, la procédure portant sur l'indemnité allouée à l'avocat d'office était onéreuse. Le président a imparti à l'avocat un nouveau délai de dix jours pour s'acquitter de l'avance de frais requise, sous peine d'irrecevabilité. L'avocat ne s'est pas exécuté.
Par décision du 31 août 2006, le président du Tribunal administratif a déclaré le recours irrecevable et mis à la charge de G._ un émolument de décision de 200 fr. et des débours par 40 fr.
C. G._ a interjeté un recours de droit administratif dans lequel il a conclu à l'annulation de la décision attaquée et au renvoi de la cause à l'autorité précédente afin qu'elle statue au fond sur son recours.
La CNA, division Assurance militaire, conclut au rejet du recours, ce que propose également l'Office fédéral de la santé publique (OFSP), Unité de direction Assurance-maladie et accidents.
D. Le 5 juillet 2007, la Ire Cour de droit social du Tribunal fédéral a tenu une audience publique.

Considérant en droit:
1. La loi du 17 juin 2005 sur le Tribunal fédéral (LTF; RS 173.110) est entrée en vigueur le 1er janvier 2007 (RO 2006 1205, 1242). L'acte attaqué ayant été rendu avant cette date, la procédure reste régie par l'OJ (art. 132 al. 1 LTF; <ref-ruling> consid. 1.2 p. 395).
2. Les décisions qui concernent l'assistance judiciaire sont des décisions d'ordonnancement de la procédure au sens de l'art. 52 al. 1 LPGA, qui ne sont pas sujettes à opposition (<ref-ruling> consid. 1 p. 155), de sorte qu'elles sont directement attaquables par la voie du recours devant les tribunaux des assurances institués par les cantons (art. 56 al. 1 et 57 LPGA). Le Tribunal administratif était dès lors compétent pour connaître de la décision du 31 mai 2006.
3. Dans la procédure administrative en matière d'assurances sociales, l'assistance gratuite d'un conseil juridique est accordée au demandeur lorsque les circonstances le justifient (art. 37 al. 4 LPGA). La LPGA a ainsi introduit une prétention légale à l'assistance juridique pour ce type de procédure (<ref-ruling> consid. 3.1 p. 155; UELI KIESER, ATSG-Kommentar, Kommentar zum Bundesgesetz über den Allgemeinen Teil des Sozialversicherungsrechts vom 6. Oktober 2000, Zurich 2003, note 16 ss ad art. 37).
Sous le régime de la LPGA, l'indemnité allouée à l'avocat d'office dans la procédure en matière d'assurances sociales ne se détermine plus selon le droit cantonal, mais en vertu du droit fédéral, par le renvoi de l'art. 55 LPGA à l'art. 65 al. 5 PA, qui renvoie à son tour à l'ordonnance du 10 septembre 1969 sur les frais et indemnités en procédure administrative (RS 172.041.0; voir à ce sujet <ref-ruling> consid. 3.1 p. 155).
4. Aux termes de l'art. 61 LPGA, sous réserve de l'art. 1er al. 3 PA, la procédure devant le tribunal cantonal des assurances est réglée par le droit cantonal; elle doit satisfaire aux exigences énumérées sous lettres a à i. Elle doit notamment être simple, rapide, en règle générale publique, ainsi que gratuite pour les parties; des émoluments de justice et les frais de procédure peuvent toutefois être mis à la charge de la partie qui agit de manière téméraire ou témoigne de légèreté (let. a).
Est donc litigieux le point de savoir si la gratuité de la procédure prévue à cette disposition vaut également dans un litige portant sur la rémunération de l'avocat d'office dans la procédure administrative en matière d'assurances sociales, autrement dit si c'est ou non à bon droit que les premiers juges ont déclaré le recours irrecevable pour défaut de paiement par le recourant d'une avance de frais.
5.1 Selon le premier juge, le principe de la gratuité de la procédure énoncé à l'art. 61 let. a LPGA a pour but de faciliter l'accès aux tribunaux des personnes qui ont souvent une situation économique précaire. Il s'applique tout spécialement dans les litiges en matière d'assurances sociales opposant un assuré à un assureur. Il ne vaut pas, en revanche, quand l'avocat d'office conteste le montant que l'assureur lui a accordé dans le cadre d'un mandat d'office. Aussi bien le premier juge a-t-il fait application du droit cantonal de procédure, notamment les art. 47 al. 5 et 52 de la loi du 27 juin 1979 sur la procédure et la juridiction administratives (LPJA/NE). Ces règles cantonales permettent au tribunal d'exiger une avance de frais et donnent la compétence à son président de déclarer un recours irrecevable si le recourant, dûment averti, ne verse pas dans le délai imparti l'avance de frais qui lui est demandée.
5.2 L'art. 61 let. a LPGA, entré en vigueur le 1er janvier 2003, a repris, sans changement par rapport à la situation antérieure, la règle de la gratuité de la procédure qui était auparavant énoncée dans les différentes lois d'assurances sociales (art. 85 aLAVS; art. 108 aLAA; art. 87 aLAMal; 103 aLACI; 106 aLAM). Par la suite, la modification de la LAI du 16 décembre 2005 (RO 2006 2003), entrée en vigueur le 1er juillet 2006, a prévu une dérogation à l'art. 61 let. a LPGA en ce sens que la procédure de recours en matière de contestations portant sur l'octroi ou le refus de prestations de l'AI devant le tribunal cantonal des assurances est soumise à des frais de justice (art. 69 al. 1bis LAI). Cette dérogation n'est pas en cause en l'espèce .
5.3 Comme l'a jugé le Tribunal fédéral des assurances à propos de l'ancien art. 108 al. 1 let. a LAA, qui avait sur le point ici en discussion le même contenu que l'art. 61 let. a LPGA, cette disposition de la LAA ne souffrait qu'une exception au principe de la gratuité de la procédure, à savoir quand une partie agit par témérité ou à la légère. Il en a déduit que, sous cette réserve, la procédure cantonale était gratuite, même si elle opposait deux assureurs (<ref-ruling>). Dans ce même arrêt, le tribunal a procédé à une analyse approfondie des travaux préparatoires de l'art. 61 let. a LPGA (la LPGA avait déjà été adoptée par le Parlement mais n'était pas encore en vigueur à cette époque). Cette analyse montre que le législateur a voulu maintenir sous le régime de la LPGA la règle de la gratuité, avec pour seule exception les cas de témérité ou de légèreté. En particulier les termes « en règle générale » (« in der Regel ») se rapportent exclusivement à la publicité des débats, mais non aux autres exigences de procédure énumérées à la lettre a de l'art. 61 LPGA (<ref-ruling> consid. 2d/cc p. 201). Par conséquent, la règle de la gratuité exprimée par cette disposition ne dépend pas de la personne qui est partie à la procédure. Elle résulte bien plutôt du fait qu'un litige est porté devant un tribunal cantonal des assurances dont la compétence se fonde sur les art. 57 et 58 LPGA. Elle vaut aussi, par ailleurs, pour les recours contre des décisions incidentes ou d'ordonnancement de la procédure prises en marge de la procédure principale (cf. <ref-ruling> consid. 3; cf. aussi THOMAS LOCHER, Grundriss des Sozialversicherungsrechts, 3e édition, Berne 2003 p. 496).
5.4 On ne voit pas de motif de faire une exception en matière de fixation des honoraires de l'avocat d'office. Celui-ci accomplit une tâche étatique spécialement régie par le droit des assurances sociales (cf. <ref-ruling> consid. 6 p. 71 et les références citées). Lors de sa désignation, il s'établit, entre l'avocat et l'assureur (dans la procédure administrative) un rapport juridique spécial en vertu duquel le premier a contre le second une prétention à être rétribué en vertu des dispositions précitées de la LPGA et de la PA. A la différence d'une activité de conseil librement consentie et pleinement rétribuée, la rémunération à laquelle peut prétendre l'avocat d'office relève du droit de procédure en matière d'assurances sociales au même titre que les litiges qui portent sur des points accessoires du procès au fond et pour lesquels la gratuité est garantie.
5.5 Par ailleurs, l'art. 61 let. a LPGA ne concerne pas seulement les litiges entre assurés et assureurs. Comme on l'a vu, il s'applique aussi aux contestations entre assureurs. Il concerne d'autres procédures où l'assuré n'est pas partie, par exemple les litiges découlant de la responsabilité de l'employeur selon l'art. 52 LAVS ou encore de la responsabilité des corporations de droit public, des organisations fondatrices privées et des assureurs à l'égard de tiers (cf. KIESER, op. cit., n. 28 ad art. 61 LPGA).
Enfin, à titre de comparaison, on observera que le Tribunal fédéral considère que la procédure instituée par l'art. 12 de la loi fédérale du 24 mars 1995 sur l'égalité entre femmes et hommes (LEg; RS 151.1) vaut pour toutes les procédures, notamment celles en matière de fixation des honoraires dus par une partie à son avocat pour la procédure devant le Tribunal fédéral prévue par l'art. 161 OJ (arrêt 4C.123/2004 du 9 juillet 2004, consid. 7).
6. En l'espèce, la décision du président du Tribunal administratif n'est pas motivée par le fait que le recourant aurait agi par témérité ou à la légère. Par conséquent, le Tribunal administratif ne pouvait, sous peine de violation du droit fédéral, exiger de lui une avance de frais et son président ne pouvait sanctionner le non-paiement de celle-ci par une décision d'irrecevabilité. Il convient, dès lors, d'annuler le jugement attaqué et de renvoyer la cause à l'autorité cantonale pour jugement au fond.
7. Dès lors que le recours ne porte pas directement sur la question de l'assistance judiciaire mais est dirigé contre un jugement d'irrecevabilité rendu par l'autorité cantonale, la procédure est onéreuse. L'intimée, qui succombe, supportera donc les frais de la procédure. Elle versera en outre des dépens au recourant pour la procédure fédérale (art. 159 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et la décision du Président du Tribunal administratif de la République et canton de Neuchâtel du 31 août 2006 est annulée.
2. La cause est renvoyée audit tribunal pour jugement au sens des motifs.
3. Les frais de justice, d'un montant de 500 fr., sont mis à la charge de la Caisse nationale suisse d'assurance en cas d'accidents (CNA), division Assurance militaire.
4. L'avance de frais versée par le recourant lui est restituée.
5. La CNA, division Assurance militaire, versera au recourant une indemnité de 2'000 fr. (y compris la taxe sur la valeur ajoutée) à titre de dépens.
6. Le présent arrêt sera communiqué aux parties, au Tribunal administratif de la République et canton de Neuchâtel et à l'Office fédéral de la santé publique.
Lucerne, le 5 juillet 2007
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier: