Faits: A. A.a Né en 1979, A.X._ est ressortissant du Kosovo. Il est arrivé en Suisse en 1998 et a été admis provisoirement jusqu'au 16 août 1999. Il serait retourné au Kosovo le 31 décembre 1999 et revenu en Suisse en novembre 2002. Il a été refoulé à Pristina le 18 mars 2003, après avoir été placé en détention préventive en raison d'une affaire de vol. Le 3 avril 2003, A.X._ a épousé au Kosovo B._, devenue B.X._. Celle-ci vit en Suisse depuis 1990 et est titulaire d'une autorisation d'établissement. A.X._ serait venu rejoindre son épouse à la fin du mois d'avril 2003. Une enfant, prénommée C._, est née de cette union, en 2003. A.b Depuis son mariage, A.X._ a subi plusieurs détentions et condamnations : - du 16 juillet au 5 septembre 2003, il a été détenu préventivement pour des affaires de vol et de conduite sans permis; - le 26 octobre 2004, il a été condamné par le Tribunal d'arrondissement de l'Est vaudois à huit mois d'emprisonnement et à quatre ans d'expulsion avec sursis pendant trois ans, ainsi qu'à une amende de 500 fr. pour recel, dénonciation calomnieuse, infractions à la loi fédérale sur la circulation routière (LCR) et à la loi fédérale sur le séjour et l'établissement des étrangers (LSEE), ainsi que contravention à la loi fédérale sur les stupéfiants (LStup.); - du 27 janvier au 22 février 2005, il a été placé en détention préventive pour des infractions à la LStup et à la LCR; - le 10 mars 2005, le Juge d'instruction du Bas-Valais l'a condamné à deux mois d'emprisonnement avec sursis pendant deux ans pour vol, infraction à la LCR et contraventions à la LStup; - le 24 janvier 2006, il a été placé en détention préventive pour vol par effraction, recel et infractions à la LStup; - le 22 octobre 2007, le Tribunal correctionnel de l'arrondissement de l'Est vaudois a admis la demande de relief présentée par A.X._ et annulé son jugement du 17 octobre 2006; statuant à nouveau il a condamné l'intéressé à une peine privative de liberté de trois ans, sous déduction de 301 jours de détention préventive; il a également révoqué les sursis accordés les 26 octobre 2004 et 10 mars 2005 et ordonné l'exécution des peines respectives de huit et deux mois d'emprisonnement; - par arrêt du 10 mars 2008, la Cour de cassation pénale du Tribunal cantonal a réformé partiellement le jugement du 22 octobre 2007 et condamné A.X._, pour vol, faux dans les certificats, dénonciation calomnieuse, infraction grave et contravention à la LStup, ainsi que violation grave des règles de la circulation routière, à une peine privative de liberté de trente-cinq mois, sous déduction de la détention préventive, la révocation des sursis précédents étant confirmée. Le 5 février 2009, le Tribunal fédéral a rejeté, dans la mesure de sa recevabilité, le recours déposé par A.X._ à l'encontre de l'arrêt du 10 mars 2008 (cause 6B_540/2008). A.c Le 10 octobre 2003, A.X._ a été rendu attentif qu'en raison de son comportement, il était possible qu'une interdiction d'entrée en Suisse et au Liechtenstein soit prononcée à son encontre. Le 24 mars 2004, le Service de la population du canton de Vaud (ci-après: le Service cantonal) a indiqué qu'il lui manquait des éléments pour statuer sur la demande d'autorisation de séjour formée par A.X._. Le 28 février 2005 et le 27 juin 2005, celui-ci a demandé au Service cantonal de statuer sur sa demande d'autorisation de séjour, indiquant qu'il avait changé et qu'il voulait montrer le bon exemple à sa fille. Le 15 août 2006, après s'être enfui du centre où il avait été placé pour soigner sa dépendance aux stupéfiants, A.X._ s'est rendu au Kosovo auprès de son père malade, qui est finalement décédé. Le 13 octobre 2006, il a déposé une demande de visa pour la Suisse. De retour en Suisse, il a été incarcéré le 13 août 2007. Le 28 avril 2008, le Service cantonal a informé A.X._ qu'il avait l'intention de refuser de lui délivrer une autorisation de séjour en raison des condamnations prononcées à son encontre. Cette procédure a été suspendue en août 2008 jusqu'à ce que le Tribunal fédéral se prononce sur le recours déposé à l'encontre du jugement du 10 mars 2008. Le 5 mars 2009, A.X._ a de nouveau demandé au Service cantonal de lui délivrer une autorisation de séjour. Le 13 mars 2009, il a été libéré conditionnellement. B. Par décision du 23 mars 2009, le Service cantonal a refusé de délivrer une autorisation de séjour en faveur de A.X._. A.X._ et son épouse B.X._ ont recouru contre cette décision auprès de la Cour de droit administratif et public du Tribunal cantonal vaudois. Par arrêt du 12 octobre 2009, le Tribunal cantonal a rejeté le recours. Il a retenu en bref que les intérêts privés des recourants ne l'emportaient pas sur l'intérêt public à ce que A.X._ ne séjourne plus en Suisse, dès lors que le recourant avait non seulement enfreint l'ordre public (art. 17 al. 2 LSEE), mais réalisait aussi un motif d'expulsion au sens de l'art. 10 al. 1 LSEE. C. A.X._ déclare déposer un recours de droit administratif, subsidiairement un recours de droit public, auprès du Tribunal fédéral. Il conclut à l'annulation de l'arrêt du 12 octobre 2009 et à l'octroi et à d'un permis de séjour. Par ordonnance du 20 novembre 2009, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif déposée par A.X._. Le Service cantonal et le Tribunal cantonal ont été invités à produire leur dossier sans échange d'écritures.