Faits: A. A._, qui n'est pas exploitant agricole, est propriétaire de la parcelle n° 75 du registre foncier de la commune de Trey, d'une surface de 9'340 m2, sise en zone agricole selon le règlement communal sur le plan d'extension et la police des constructions de la commune de Trey, adopté par le Conseil d'Etat du canton de Vaud le 16 février 1979 (RPE). Ce bien-fonds supporte notamment une maison familiale, une petite dépendance autorisée au titre de "cabanon de jardin" et une surface de 8'483 m2 en pré-champ qui permet aux animaux domestiques (biches, ânes et moutons) détenus par le propriétaire de pâturer dans l'enclos qui leur est réservé à cet effet. Le frère du prénommé, B._, exploite un centre équestre à Corserey dans le canton de Fribourg, à environ 6 kilomètres de Trey. Le centre équestre, sis en "zone centre équestre" selon le plan d'affectation communal de Corserey, comporte notamment un manège, une écurie et une buvette. B._ cultive également des surfaces agricoles aux alentours. B. Le 18 août 2006, A._ a déposé une demande de permis de construire une écurie destinée à abriter deux chevaux pour le compte de B._. Il a expliqué que l'Etat de Fribourg avait rendu un préavis négatif à la demande d'agrandissement du manège de son frère, au motif que le taux d'occupation de la zone ne serait plus respecté. Il a précisé que son frère disposait alors de trois mulets et de quarante-huit chevaux, dont dix étaient détenus en propriété pour la formation des jeunes et le reste en pension. Il a déposé un rapport agronomique établi par la société X._, daté du 13 mars 2006, et relatif aux besoins en fourrage pour la garde des animaux des deux frères. Selon ce rapport, B._ exploitait un domaine de 12,06 hectares de surface agricole utile, surface destinée entièrement à la production de fourrage pour les chevaux. La surface cultivée ne permettait cependant plus de couvrir la consommation, ce qui rendait l'achat de fourrage nécessaire. Or, 60 dt de matière sèche (incluant deux hectares de parcelles appartenant à des voisins) restaient à disposition chez A._. B._ pourrait ainsi déplacer à Trey deux chevaux, ce qui aurait pour avantage de résoudre partiellement le problème du manque de place et de tirer pleinement profit des surfaces disponibles à Trey. A cette fin, B._ pourrait prendre en location une surface de 5'000 m2 de A._, ainsi que les parcelles mises à disposition par les voisins de celui-ci. Deux baux à ferme ont été conclus le 26 mars 2006, l'un entre B._ et les copropriétaires de la parcelle voisine, l'autre entre les deux frères A._ et B._. Le 20 novembre 2006, deux représentants du Service du développement territorial du canton de Vaud (ci-après: le Service du développement territorial) se sont rendus sur la parcelle n° 75 et ont constaté que l'écurie avait déjà été construite, dans sa majeure partie, et que diverses dépendances avaient été aménagées sur le terrain. Par décision du 19 décembre 2006, le Service du développement territorial a refusé de délivrer l'autorisation requise et ordonné la remise en état des lieux (démolition, évacuation complète de la dépendance et remise en état du sol). Seul un abri à daims fermé pouvait être toléré. Le Service de l'agriculture du canton de Vaud était au contraire favorable au projet de construction. Par décision du 11 janvier 2007, la municipalité de Trey a ordonné à A._ de procéder à la démolition de l'écurie, à la "végétalisation" de l'espace de terrain avant le 1er mai 2007 et à la suppression des dépendances érigées sans autorisation jusqu'au 20 avril 2007. C. Par acte du 31 janvier 2007, A._ et B._ ont déposé un recours contre la décision du Service du développement territorial du 19 décembre 2006 et contre celle de la municipalité du 11 janvier 2007, 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). Le 9 janvier 2008, les juges cantonaux ont tenu une audience et procédé à une inspection locale en présence des parties. Par arrêt du 22 janvier 2009, le Tribunal cantonal a admis partiellement le recours, annulé les décisions attaquées et renvoyé le dossier au Service du développement territorial et à la municipalité pour nouvelles décisions au sens des considérants. Il a considéré en substance que l'abri à daims, la mangeoire ainsi que l'abri à moutons et ânes pouvaient être régularisés, alors que l'écurie à chevaux, l'agrandissement à l'arrière de l'abri à daims et le bûcher étaient dans leur intégralité illicites et devaient être démolis. D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent principalement au Tribunal fédéral de réformer l'arrêt du Tribunal cantonal du 22 janvier 2009 en ce sens que l'autorisation de construire sollicitée pour la construction d'une écurie pour deux chevaux soit délivrée. Ils concluent subsidiairement à l'annulation de l'arrêt attaqué. Ils se plaignent notamment d'une violation de l'art. 16a de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700). Le Tribunal cantonal et l'Office fédéral du développement territorial concluent au rejet du recours. La municipalité de Trey s'en rapporte aux écritures produites par le Service du développement territorial, lequel conclut au rejet du recours et s'en remet à justice pour juger si l'arrêt attaqué peut ou devrait être réformé in pejus en confirmant l'ordre initial des autorités communales et cantonales de démolir l'abri à moutons et à ânes. Par courrier du 1er juillet 2009, le Tribunal cantonal précise ne pas s'opposer à l'admission des conclusions du Service du développement territorial tendant à la reformatio in pejus de l'arrêt attaqué. A._ et B._ se sont prononcés sur ces déterminations. E. Par ordonnance du 24 mars 2009, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif, présentée par les recourants.