Faits:
A. C._ est propriétaire de la parcelle n° 568 du registre foncier de la Tour-de-Peilz (VD), sur laquelle est bâtie une maison d'habitation agrémentée d'une piscine. Une haie séparait ce bien-fonds de la parcelle voisine n° 569, propriété de A._ et B._ (ci-après: les époux A._). Désireux de remplacer cette haie par une palissade, C._ a contacté le Service de l'urbanisme et des travaux publics de la Tour-de-Peilz (devenu "Direction de l'urbanisme et des travaux publics"; ci-après: le service de l'urbanisme). La réponse qu'il a reçue laissant croire que ce projet pouvait être réalisé sans mise à l'enquête publique, C._ a arraché la haie et réalisé la palissade. Interpellé par les époux A._, le Service cantonal de l'aménagement du territoire a estimé que l'ouvrage en question aurait dû faire l'objet d'une enquête publique. Se fondant sur cet avis, la Municipalité de la Tour-de-Peilz (ci-après: la municipalité) a, par courrier du 3 septembre 2002, requis C._ de régulariser la construction litigieuse par le biais d'une mise à l'enquête publique et lui a imparti un délai pour déposer un dossier à cette fin. Par décision du 14 novembre 2002, la municipalité a confirmé l'exigence d'une mise à l'enquête publique. Par arrêt du 13 mai 2006, le Tribunal administratif du canton de Vaud a rejeté le recours formé par C._ contre cette décision. La Cour de céans a confirmé cet arrêt le 18 octobre 2006 (arrêt 1P.373/2006).
B. C._ a alors déposé une demande de permis de construire. Il ressort des plans annexés à la demande que la palissade a une longueur de 22,75 m et une hauteur maximale de 2,80 m à compter du remblai aménagé sur la parcelle du constructeur, voire de 3,60 m à compter du terrain des époux A._. Mis à l'enquête publique du 21 mars au 19 avril 2007, le projet a suscité diverses oppositions, dont celle des époux A._. Par décision du 10 juillet 2007, la municipalité a écarté les oppositions et délivré le permis de construire. Les époux A._ ont recouru contre cette décision auprès du Tribunal administratif du canton de Vaud (devenu la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud; ci-après: le Tribunal cantonal), qui a rejeté ce recours par arrêt du 16 décembre 2008. En substance, cette autorité a considéré que le dossier de mise à l'enquête était complet, que l'arrachage de la haie n'était pas soumis à autorisation, que les dimensions de la palissade étaient conformes à l'art. 39 du règlement d'application de la loi cantonale sur l'aménagement du territoire et les constructions (RATC; RSV 700.11.1) et à l'art. 82 du règlement sur le plan d'extension et la police des constructions de la commune de la Tour-de-Peilz du 5 juillet 1972 (ci-après: le règlement communal). Procédant à une pesée des intérêts en présence, le Tribunal cantonal a en outre considéré que la palissade litigieuse était "supportable sans sacrifice excessif" de la part des voisins, de sorte que la condition de l'art. 39 al. 4 RATC était respectée.
C. Agissant seuls, A._ et B._ forment un recours au Tribunal fédéral à l'encontre de cet arrêt. Ils concluent à l'annulation de l'arrêt attaqué et de la décision de la municipalité du 10 juillet 2007, ainsi qu'au renvoi de la cause à l'autorité inférieure pour qu'elle impose à la municipalité de se prononcer également sur l'arrachage de la haie, subsidiairement sur la hauteur de l'ouvrage litigieux. Ils se plaignent en substance d'une application arbitraire (art. 9 Cst.) des règles sur la hauteur et sur le préjudice, ainsi que d'une violation de leur droit d'être entendus (art. 29 al. 2 Cst.) en raison d'un défaut de motivation. C._ et la Municipalité de la Tour-de-Peilz se sont déterminés; ils concluent au rejet du recours, dans la mesure de sa recevabilité. Le Tribunal cantonal se réfère aux considérants de son arrêt. A._ et B._ ont présenté des observations complémentaires.

Considérant en droit:
1. Les recourants n'ont pas intitulé leur recours. Le défaut d'intitulé ou l'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (<ref-ruling> consid. 1.2 p. 382 et les arrêts cités). 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 ont pris part à la procédure de recours devant le Tribunal cantonal et sont particulièrement touchés par l'arrêt attaqué, qui confirme l'autorisation de construire une palissade aux dimensions imposantes à la limite de leur parcelle. Ils ont donc la qualité pour agir au sens de l'<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. Les conclusions du recours demandant d'imposer à la municipalité de se prononcer également sur l'arrachage de la haie, subsidiairement sur la hauteur de l'ouvrage litigieux, n'ont pas été présentées devant le Tribunal cantonal. Devant cette instance, les recourants se limitaient en effet à demander l'annulation de l'autorisation de construire du 10 juillet 2007 et la remise en état des lieux. Il s'agit donc de conclusions nouvelles, qui sont irrecevables (<ref-law>).
3. Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, les recourants se plaignent d'une violation de leur droit d'être entendus en raison d'un défaut de motivation de l'arrêt attaqué.
3.1 Le droit d'être entendu, tel qu'il est garanti à l'art. 29 al. 2 Cst., confère à toute personne le droit d'exiger, en principe, qu'un jugement ou une décision défavorable à sa cause soit motivé. Cette garantie tend à éviter que l'autorité ne se laisse guider par des considérations subjectives ou dépourvues de pertinence; elle contribue ainsi à prévenir une décision arbitraire. L'objet et la précision des indications à fournir dépend de la nature de l'affaire et des circonstances particulières du cas; néanmoins, en règle générale, il suffit que l'autorité mentionne au moins brièvement les motifs qui l'ont guidée (<ref-ruling> consid. 2b p. 109; voir aussi <ref-ruling> consid. 3.3 p. 445; <ref-ruling> consid. 2b p. 102; <ref-ruling> consid. 2c p. 372). L'autorité peut se limiter à l'examen des questions décisives pour l'issue du litige; il suffit que le justiciable puisse apprécier correctement la portée de la décision et l'attaquer à bon escient et que l'autorité de recours puisse exercer son contrôle (<ref-ruling> consid. 3.1 p. 277; <ref-ruling> consid. 4.3 p. 540; <ref-ruling> consid. 2c p. 372 et les références).
3.2 En l'occurrence, les recourants invoquent "l'absence de motivation, même succincte, du jugement attaqué", au motif que l'autorité compétente n'aurait pas expliqué "la raison pour laquelle il se justifie de consentir, a posteriori, en lieu et place d'une haie vive non replantée, à l'édification d'un ouvrage imposant [...]". Il ressort cependant de l'arrêt attaqué que le Tribunal cantonal a exposé les motifs pour lesquels il avait considéré que la palissade litigieuse était conforme aux dispositions légales applicables. Il a également expliqué pourquoi l'arrachage de la haie n'était pas soumis à autorisation. Enfin, il a procédé à un examen circonstancié des intérêts en présence, pour conclure que le préjudice subi par les recourants du fait de la construction en cause n'était pas insupportable au point d'entraîner le rejet de la demande de permis de construire. Le fait que les recourants "expriment leur consternation" au sujet des considérants de l'arrêt attaqué n'enlèvent rien au fait que celui-ci satisfait aux exigences de motivation susmentionnées. En effet, les questions décisives pour l'issue du litige ont été examinées et les recourants étaient en mesure de comprendre les motifs qui ont guidé l'autorité et de les contester. Ce premier moyen doit donc être rejeté.
4. Invoquant l'art. 9 Cst., les recourants se plaignent d'arbitraire dans l'appréciation des preuves et l'établissement des faits, ainsi que dans l'application de règles de droit cantonal ou communal.
4.1 Selon la jurisprudence, l'appréciation des preuves ou l'établissement des faits sont arbitraires (art. 9 Cst.; pour une définition de l'arbitraire cf. <ref-ruling> consid. 3.1 p. 265 s.; <ref-ruling> consid. 3.1 p. 153) lorsque l'autorité n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si elle ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision ou lorsqu'elle tire des constatations insoutenables des éléments recueillis (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41). Appelé à revoir l'application ou l'interprétation d'une norme sous l'angle de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs et en violation d'un droit certain. En revanche, si l'application de la loi défendue par l'autorité cantonale ne s'avère pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - éventuellement plus judicieuse - paraît possible (<ref-ruling> consid. 4.1 p. 133; <ref-ruling> consid. 5.1 p. 260 s. et les arrêts cités).
4.2 Les recourants critiquent d'abord la détermination de la hauteur de l'ouvrage litigieux. En substance, ils font grief au Tribunal cantonal de s'être référé au jugement du 17 octobre 2001 du Tribunal d'arrondissement de l'est vaudois, qui avait considéré que la hauteur de la palissade était conforme à la législation applicable. Or, le tribunal d'arrondissement avait calculé la hauteur de 2,80 m depuis le remblai situé sur la parcelle de l'intimé, alors que les recourants allèguent que le point le plus haut de la palissade atteindrait 3,60 m en partant de leur parcelle. Le tribunal d'arrondissement a cependant considéré qu'il convenait de prendre comme base de mesure la parcelle du constructeur, car la palissade y était entièrement construite. Le Tribunal cantonal s'estime lié par ce jugement civil, au motif que l'application de dispositions du code rural et foncier du canton de Vaud du 7 décembre 1987 (CRF; RSV 211.41) est en jeu. Il se fonde sur sa propre jurisprudence et sur la doctrine pour retenir que l'application de l'art. 32 CRF relève du contentieux civil et échappe à sa cognition. Ce dernier point n'étant pas discuté, il y a lieu de s'en tenir à l'appréciation des juges cantonaux à cet égard. Ainsi, même si la manière de calculer la hauteur de la palissade peut paraître a priori discutable, il n'est pas démontré que le Tribunal cantonal a fait preuve d'arbitraire en s'estimant lié par l'appréciation du juge civil.
Par ailleurs, les recourants entendent se prévaloir d'un passage de l'arrêt attaqué rapportant que la hauteur de 3,60 m avait été constatée "depuis le niveau du sol du côté de la parcelle n° 568", ce qui correspond au bien-fonds de l'intimé. Il s'agit cependant à l'évidence d'une erreur de plume et il ressort clairement du dossier, en particulier du procès-verbal de l'inspection locale, que le Tribunal cantonal voulait en réalité parler de la parcelle n° 569, propriété des recourants. Cette erreur sans incidence ne saurait dès lors fonder une constatation arbitraire des faits.
4.3 Les recourants s'en prennent également à la manière de mesurer la hauteur des parties pleines de la palissade, qui ne doivent pas dépasser 1 m en vertu de l'art. 82 du règlement communal sur les constructions. Lors de l'inspection locale du 25 novembre 2008, les juges cantonaux auraient constaté que la hauteur des parties pleines atteignait 1,12 m par endroits. Cela étant, cette hauteur était atteinte en prenant en compte les planches de soutènement visibles depuis la parcelle des recourants. Or, l'arrêt attaqué précise que ces planches "ne servent qu'à retenir la terre de la parcelle amont, le terrain étant à l'origine en pente, et se distinguent ainsi clairement de la palissade". S'il est vrai que cette appréciation peut être discutée et qu'il aurait également été envisageable de prendre en compte les planches de soutènement, cela ne suffit pas pour considérer que l'arrêt entrepris est déraisonnable ou manifestement insoutenable au sens de la jurisprudence susmentionnée. Il convient donc de constater que la juridiction cantonale n'a pas abusé de son pouvoir d'appréciation en la matière et que sa décision échappe sur ce point au grief d'arbitraire.
4.4 Les recourants se plaignent en outre implicitement d'une application arbitraire de l'art. 51 al. 3 du règlement communal en relation avec l'arrachage de la haie qui était située à l'emplacement de la palissade litigieuse. Cette disposition a la teneur suivante: "Il ne peut être abattu aucun arbre d'essence majeure, cordon boisé, boqueteau et haie vive, sans autorisation de la Municipalité. [...]". Le Tribunal cantonal a considéré que la haie arrachée par l'intimé était composée de thuyas - essence qui n'est pas indigène - et qu'elle ne constituait pas une haie vive susceptible de protection sur la base de la loi cantonale du 10 décembre 1969 sur la protection de la nature, des monuments et des sites (LPNMS; RSV 450.11). Quand bien même la haie en cause aurait été composée non seulement de thuyas mais aussi, comme l'allèguent les recourants, de laurel et de buis, cela ne démontre pas qu'il s'agissait d'une "haie vive" digne d'être protégée. Par ailleurs, s'il est vrai que les explications de la municipalité au sujet d'une prétendue maladie de la haie apparaissent surprenantes et qu'elles ne sont pas établies par pièces, cela ne prouve pas pour autant que l'arrachage était soumis à autorisation. Pour le surplus, les recourants ne démontrent aucunement que la disposition invoquée ait été appliquée de manière arbitraire.
4.5 Enfin, les recourants s'en prennent à l'application de l'art. 39 al. 4 RATC, qui prévoit que des dépendances ne peuvent être autorisées "que pour autant qu'elles n'entraînent aucun préjudice pour les voisins". Comme rappelé ci-dessus (cf. supra consid. 3.2), le Tribunal cantonal a examiné cette question de manière circonstanciée. Il a constaté que la palissade litigieuse était certes d'une "hauteur inhabituelle", mais que le préjudice subi par les recourants se limitait à une "impression d'écrasement" lorsqu'ils accédaient à leur maison, étant précisé que les pièces de vie et le jardin ne donnaient pas sur la construction litigieuse. Se fondant sur la jurisprudence cantonale, l'autorité intimée a considéré que cet inconvénient ne constituait pas un préjudice excessif au sens de l'art. 39 al. 4 RATC. Dans la pesée des intérêts en présence, il a également pris en compte le fait que la palissade avait l'avantage de créer une séparation marquée entre les parcelles de voisins entretenant depuis longtemps des relations conflictuelles, ce qui ne prête pas le flanc à la critique sur le vu du dossier. Pour le surplus, les recourants ne contestent pas la pesée des intérêts de manière convaincante et ils ne démontrent pas en quoi le Tribunal cantonal aurait fait preuve d'arbitraire à cet égard.
5. Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité. Les recourants, qui succombent, doivent supporter les frais de la présente procédure (<ref-law>). Ils verseront en outre une indemnité à titre de dépens à l'intimé, qui obtient gain de cause avec l'assistance d'un avocat (<ref-law>). En revanche, il n'est pas alloué de dépens à la Municipalité de la Tour-de-Peilz (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté, dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants.
3. Une indemnité de 1'500 fr. est allouée à l'intimé à titre de dépens, à la charge des recourants.
4. Le présent arrêt est communiqué aux recourants, aux mandataires de l'intimé et de la Municipalité de la Tour-de-Peilz, ainsi qu'au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public.
Lausanne, le 10 juin 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener