Faits:
A. C._ est propriétaire de la parcelle n° 16'137 du registre foncier de la commune de Sion. Le 12 juillet 2007, il a requis l'autorisation de construire une maison individuelle sur ce bien-fonds, sis en zone à bâtir. Mis à l'enquête publique par avis paru au Bulletin officiel du canton du Valais du 27 juillet 2007, ce projet a suscité l'opposition de B._, propriétaire de la parcelle voisine n° 14'059. Par décision du 25 octobre 2007, le Conseil communal de Sion a délivré le permis de construire et rejeté l'opposition de la prénommée. Cette décision a été notifiée le 14 février 2008 seulement.
Dans l'intervalle, le 9 janvier 2008, B._ a signé avec A._ une "promesse de vente et d'achat et pacte d'emption" (ci-après: la promesse de vente) portant sur la parcelle n° 14'059, pour la durée d'une année prolongeable à la demande du promettant-acquéreur jusqu'au 1er janvier 2010. Ce document comportait la clause suivante:
Le bénéficiaire du droit d'emption est autorisé à entreprendre, à ses frais, toutes démarches en vue de la mise en valeur de la parcelle n° 14'059 (procédure d'autorisation de construire, division de la parcelle, obtention d'une servitude de passage et d'accès à la parcelle, opposition et négociation pour les projets des parcelles voisines, en particulier pour l'opposition à la construction sur la parcelle voisine n° 16'137, etc.).
Le 20 mars 2008, B._ a recouru contre l'autorisation de construire auprès du Conseil d'Etat du canton du Valais, qui a rejeté le recours par décision du 16 décembre 2008.
B. Par écriture du 29 janvier 2009, se prévalant des droits conférés par la promesse de vente susmentionnée, A._ a recouru contre cette décision auprès du Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal). Le 2 février 2009, le mandataire du prénommé, Me X._, a écrit au Tribunal cantonal que B._, "au nom et pour le compte de laquelle agit A._", était recourante. Par courrier du 3 février 2009, le mandataire de cette dernière, Me Y._, a écrit au Tribunal cantonal que le courrier précité de Me X._ signifiait que le recours du 29 janvier 2009 était aussi interjeté par B._.
Par arrêt du 29 mai 2009, le Tribunal cantonal a déclaré le recours irrecevable. Il a considéré en substance que A._ n'était pas partie à la procédure devant le Conseil d'Etat, de sorte qu'il n'avait pas la qualité pour recourir, conformément à l'art. 44 al. 2 de la loi du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA; RS/VS 172.6), applicable par renvoi de l'art. 80 al. 1 let. a LPJA. Quant à B._, elle n'avait déposé aucun recours satisfaisant aux exigences de l'art. 47 al. 2 LPJA. De plus, Me X._ n'avait jamais prétendu avoir été mandaté par elle pour agir en son nom et A._ n'apparaissant pas comme son représentant valablement désigné.
C. Agissant par la voie du recours en matière de droit public, B._ et A._ demandent au Tribunal fédéral d'annuler cet arrêt et de renvoyer la cause au Tribunal cantonal pour nouvelle décision. Ils se plaignent de formalisme excessif (art. 29 Cst.) et d'une violation du principe de la bonne foi (art. 5 et 9 Cst.). Ils requièrent en outre l'octroi de l'effet suspensif. Le Conseil d'Etat et C._ se sont déterminés; ils concluent au rejet du recours. Renonçant à formuler des observations, la Commune de Sion conclut néanmoins au rejet du recours. Le Tribunal cantonal a renoncé à se déterminer.
D. Par ordonnance du 25 août 2009, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.

Considérant en droit:
1. Dirigé contre une décision rendue dans le domaine du droit public des constructions, le recours est recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Les recourants se plaignent d'avoir été privés de la possibilité de prendre part à la procédure devant l'autorité précédente et ils sont particulièrement touchés par l'arrêt attaqué, qui leur dénie la qualité pour recourir. Ils ont donc un intérêt digne de protection à obtenir l'annulation ou la modification de cet arrêt, de sorte que la qualité pour recourir doit leur être reconnue (<ref-law>). Pour le surplus, interjeté en temps utile et dans les formes requises contre une décision finale prise en dernière instance cantonale non susceptible de recours devant le Tribunal administratif fédéral, le recours est recevable au regard des art. 42, 86 al. 1 let. d, 90 et 100 al. 1 LTF.
2. Invoquant l'art. 29 al. 2 Cst., les recourants font grief au Tribunal cantonal d'avoir fait preuve de formalisme excessif en déclarant leurs recours irrecevables.
2.1 Le formalisme excessif est un aspect particulier du déni de justice prohibé par l'art. 29 al. 2 Cst. Il est réalisé 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, 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. 5.4.1 p. 183; <ref-ruling> consid. 2a p. 142; <ref-ruling> consid. 2a/bb p. 34 et les arrêts cités). En tant qu'elle sanctionne un comportement répréhensible de l'autorité dans ses relations avec le justiciable, l'interdiction du formalisme excessif poursuit le même but que le principe de la bonne foi (art. 9 Cst.). A cet égard, elle commande à l'autorité d'éviter de sanctionner par l'irrecevabilité les vices de procédure aisément reconnaissables qui auraient pu être redressés à temps, lorsque celle-ci pouvait s'en rendre compte assez tôt et les signaler utilement au plaideur (<ref-ruling> consid. 3a p. 170; <ref-ruling> consid. 4a p. 270 et les références).
2.2 En l'occurrence, on peine à comprendre pour quelles raisons les recourants se plaignent de formalisme excessif en ce qui concerne l'irrecevabilité du recours de A._. En effet, l'art. 44 al. 2 LPJA - applicable par renvoi de l'art. 80 al. 1 let. a LPJA - est clair: "n'a pas qualité pour recourir celui qui a négligé d'agir devant une instance inférieure alors qu'il en avait la possibilité". Or, il n'est pas contesté que A._ n'a pas recouru devant le Conseil d'Etat et les recourants n'allèguent pas qu'il aurait été privé de la possibilité de le faire. C'est en vain que les recourants se réfèrent à une prétendue substitution du prénommé à B._ dans la procédure devant le Tribunal cantonal, dans la mesure où ils ne démontrent pas la validité de ce procédé au regard de la norme de procédure précitée, dont ils n'invoquent au demeurant pas une application arbitraire. Les recourants ne sauraient être suivis lorsqu'ils prétendent que le Tribunal cantonal devait démontrer en quoi la substitution n'avait pas été "effectuée de plein droit". C'est au contraire à l'intéressé qu'il incombait d'établir que le procédé en question lui conférait la qualité pour recourir nonobstant la règle claire de l'art. 44 al. 2 LPJA. Dans ces conditions, le Tribunal cantonal n'a fait preuve d'aucun formalisme excessif dans l'application de cette disposition.
2.3 La situation est plus confuse s'agissant de l'irrecevabilité du recours de B._. En effet, les recourants prétendent en substance que la prénommée s'est ralliée au recours de A._. Or, si ce dernier cite la promesse de vente du 9 janvier 2008 dans son écriture, il n'y précise pas qu'il agit au nom de B._ ou que celle-ci s'associe au recours. Par ailleurs, la prénommée n'a pas produit une écriture de recours séparée, si bien que le juge instructeur l'a simplement invitée à déposer une réponse. Réalisant sans doute que les intentions des parties n'étaient pas bien comprises du juge instructeur, Me X._ lui a adressé un courrier le 2 février 2009. Les explications données dans cette lettre ne sont cependant guère plus claires, puisqu'il y est mentionné pêle-mêle que B._ est représentée par Me Y._, que A._ "agit au nom et pour le compte" de celle-ci et qu'il "prend maintenant le relai", d'entente avec elle, pour la procédure de recours devant le Tribunal cantonal. Le courrier se termine par la mention du fait que B._ "est recourante", sans que l'avocat ne précise si l'intéressée se rallie au recours déposé ou si elle a l'intention de recourir par l'intermédiaire de son propre avocat. Toutefois, par courrier du 3 février 2009, Me Y._ a indiqué que le recours du 29 janvier 2009 était aussi interjeté par sa cliente, qui avait jugé opportun de confier ses intérêts à Me X._. Au terme de ce courrier figure en outre un post scriptum selon lequel B._ serait prête à délivrer "toute procuration supplémentaire".
Contrairement à ce que semblent croire les recourants, on ne peut pas toujours attendre du juge qu'il devine les véritables intentions des parties en décryptant les formulations sibyllines utilisées par leurs avocats. Cela étant, il ressort du courrier déposé par Me Y._ le 3 février 2009, dans le délai de recours, que B._ a manifesté sa claire volonté de recourir contre la décision du Conseil d'Etat, en faisant sien le recours déposé initialement par A._ et en confiant la défense de ses intérêts à Me X._. A cet égard, l'argument du Tribunal cantonal selon lequel B._ ne se trouve pas dans la même situation juridique que A._ est sans pertinence s'agissant de la qualité pour recourir, qui se distingue de l'examen des griefs sur le fond. Dès lors qu'il était clair que B._ entendait adhérer au recours déposé par Me X._, le Tribunal cantonal pouvait interpeller ce mandataire pour qu'il produise une procuration susceptible de régulariser cette démarche (art. 11 LPJA). Même si les avocats des intéressés ont agi avec passablement d'imprécisions et de légèreté, il n'y avait pas lieu pour autant de sanctionner d'irrecevabilité le recours de la prénommée pour le seul défaut de procuration. Un tel vice est en effet réparable - même après l'échéance du délai de recours - et aucun intérêt public ne justifiait un refus d'entrer en matière pour ce motif (cf. arrêts 2P.329/2005 du 12 juin 2006 consid. 2.2 publié in RF 2007 p. 305; 4C.236/2003 du 30 janvier 2004 consid. 3.3 et 3.4). Dans ces conditions, en considérant que le recours de B._ n'avait pas été "valablement interjeté dans les formes ou par un représentant correctement désigné et mandaté" sans lui donner l'occasion de réparer ce vice, le Tribunal cantonal a fait preuve de formalisme excessif.
3. Il s'ensuit que le recours doit être partiellement admis et l'arrêt attaqué annulé en tant qu'il déclare irrecevable le recours de B._. La cause est renvoyée au Tribunal cantonal pour qu'il rende une nouvelle décision, le cas échéant après avoir exigé du mandataire de B._ qu'il justifie ses pouvoirs par une procuration écrite. Dès lors que la présente procédure est notamment due à la confusion créée par les recourants, il se justifie de mettre une partie des frais à leur charge (<ref-law>). Dans la mesure où ils obtiennent partiellement gain de cause pour des motifs d'ordre formel, les recourants ont droit à des dépens réduits, à la charge de l'Etat du Valais. L'intimé ayant lui aussi partiellement gain de cause, ses dépens sont compensés avec ceux qu'il doit aux recourants (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis. L'arrêt attaqué est annulé en tant qu'il déclare irrecevable le recours de B._ et la cause est renvoyée au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Il est rejeté pour le surplus.
2. Les frais judiciaires sont mis à la charge des recourants à concurrence de 1'000 fr.
3. Une indemnité de 1'000 fr. est allouée aux recourants à titre de dépens, à la charge de l'Etat du Valais.
4. Il n'est pas alloué de dépens à l'intimé C._.
5. Le présent arrêt est communiqué aux mandataires des parties, à la Commune de Sion ainsi qu'au Conseil d'Etat et au Tribunal cantonal du canton du Valais.
Lausanne, le 24 septembre 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener