Faits: A. R._, né en 1937, marié, a été mis au bénéfice de prestations complémentaires cantonales et fédérales à la suite d'une demande déposée en 1995. Par décision du 29 mars 2007, l'Office cantonal des personnes âgées (OCPA; depuis le 1er mai 2008, le Service des prestations complémentaires, ci-après: SPC) a constaté que l'assuré n'avait plus droit aux prestations complémentaires fédérales et que son droit aux prestations complémentaires cantonales s'élevait à 950 fr. par mois à partir du 1er avril 2007. Dans le nouveau calcul, l'OCPA a pris en compte, outre un gain de 12'031 fr. généré par l'activité lucrative de l'épouse, un gain potentiel de cette dernière estimé à 27'825 fr. Cette décision n'a pas été attaquée. Par lettre du 22 octobre 2007, l'assuré a sollicité des prestations d'assistance pour lui-même et son épouse, laquelle était en arrêt de travail depuis deux semaines pour cause de maladie. Par décision du 30 octobre 2007, l'OCPA a refusé d'allouer à l'assuré des prestations d'assistance. Il a cependant tenu compte de l'augmentation de son loyer depuis le 1er avril 2007 et lui a octroyé des prestations complémentaires cantonales de 966 fr. par mois à partir du 1er novembre 2007. L'assuré n'avait en revanche pas droit à des prestations complémentaires fédérales. Par lettre du 8 novembre 2007, l'assuré s'est opposé à cette décision. Il contestait la prise en compte d'un gain potentiel de son épouse de 27'825 fr., laquelle, âgée de 52 ans, était inscrite à l'Office cantonal de l'emploi auprès duquel elle devait justifier chaque mois de recherches de travail actives. Celles-ci n'avaient pas encore été fructueuses, de sorte qu'on ne pouvait reprocher à son épouse de ne pas mettre à profit sa capacité de gain. L'OCPA a rejeté l'opposition par une nouvelle décision du 3 janvier 2008. B. Par lettre du 9 janvier 2008, R._ a contesté cette décision. L'OCPA a transmis cette lettre au Tribunal des assurances sociales du canton de Genève comme objet de sa compétence. L'assuré a complété son recours le 4 février 2008. Statuant le 13 janvier 2009, le tribunal cantonal a admis le recours, annulé les décisions des 30 octobre 2007 et 3 janvier 2008 s'agissant du gain potentiel de l'épouse et renvoyé la cause au SPC pour nouvelle décision au sens des considérants. En bref, il a retenu que l'épouse de l'assuré avait, dès le mois de novembre 2007, activement cherché un emploi à plein temps, de sorte qu'elle ne s'était nullement abstenue d'exercer une activité lucrative ni d'étendre une telle activité. Par conséquent, c'était à tort que l'OCPA avait inclus, dans le calcul des prestations dues à l'assuré à partir du 1er novembre 2007, un gain potentiel de son épouse. C. Le SPC interjette un recours en matière de droit public contre ce jugement en concluant à l'annulation de celui-ci et au rétablissement de sa décision sur opposition du 3 janvier 2008. Il a par ailleurs sollicité l'effet suspensif à son recours, ce qui lui a été accordé par ordonnance du 15 avril 2009. R._ conclut principalement à l'irrecevabilité du recours et subsidiairement à son rejet. L'Office fédéral des assurances sociales (OFAS) ne s'est pas déterminé.