Faits: A. X._, ressortissant marocain, est prévenu, depuis le 20 mars 2013, notamment de vols, de dommages à la propriété et de violations de domicile. Il lui est reproché d'avoir, en juillet 2012, cambriolé deux appartements et dérobé divers objets d'une valeur totale estimée à 10'000 francs. Par ordonnance du 21 mars 2013, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a ordonné la mise en détention provisoire de X._ pour deux mois, en raison des risques de fuite et de réitération. Par ordonnance du 2 avril 2013, le Tmc a rejeté la demande de mise en liberté formée par le recourant le 25 mars 2013. La Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours interjeté par le prévenu contre cette ordonnance, par arrêt du 19 avril 2013. Elle a considéré en substance que les charges étaient suffisantes, qu'il existait un risque de récidive et de fuite et que la caution de 8'000 francs était insuffisante. B. Agissant par la voie du recours en matière pénale, X._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 19 avril 2013 et d'ordonner sa mise en liberté immédiate, conditionnée cas échéant au dépôt d'une caution de 8'000 francs. Il conclut subsidiairement au renvoi de la cause à la Cour de justice pour nouvelle décision au sens des considérants. Le Ministère public du canton de Genève conclut au rejet du recours. La Cour de justice se réfère aux considérants de son arrêt et renonce à formuler des observations. Le recourant a répliqué par courrier du 13 mai 2013. 