Faits: A. Le 24 août 2011, A._ et un comparse ont été interpellés par la police genevoise, à la suite d'une tentative de cambriolage. Ils ont été relaxés, sans avoir été mis en détention préventive. La procédure pénale, ouverte pour ces faits, porte le numéro P/12264/2011. Le 10 octobre 2011, une tentative de cambriolage a été commise à Meyrin. Dans un véhicule retrouvé à proximité des lieux, la police a découvert un téléphone portable appartenant à B._, ressortissant roumain, défavorablement connu des services de police pour cambriolages. Trois jours plus tard, A._ a été arrêté à proximité d'un lieu où une tentative de cambriolage a été dénoncée. Ne pouvant être directement impliqué, il a été relâché. A._ a été interpellé une nouvelle fois le 17 octobre 2011. Il a été prévenu de vol, de dommage à la propriété et de violation de domicile pour avoir, de concert avec des tiers, cambriolé une station-service à Meyrin en y emportant un coffre-fort contenant environ 8'000 francs ainsi que trois cartouches de cigarettes. Un chien policier avait suivi une trace et avait retrouvé le prénommé. Une analyse des traces de chaussures concluait qu'il était possible que la trace prélevée sur les lieux du cambriolage ait été laissée par la chaussure gauche portée par l'intéressé lors de son interpellation. Une procédure pénale a été ouverte pour ces faits, sous la référence P/14657/2011. La page de garde du dossier de procédure mentionne que la procédure P/14657/2011 a été jointe à la procédure P/12264/2011 le 27 octobre 2011. B. Par arrêt du 13 février 2012 (arrêt 1B_44/2012), le Tribunal fédéral a confirmé la décision du Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) et celle de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) de maintenir l'intéressé en détention préventive jusqu'au 1er février 2012, notamment en raison des risques de fuite. C. Le 31 janvier 2012, le Tmc a rendu une ordonnance de prolongation de la détention provisoire jusqu'au 1er mars 2012, en raison des risques de collusion, de fuite et de réitération. Statuant sur recours de l'intéressé, la Cour de justice a confirmé cette ordonnance par arrêt du 10 février 2012. D. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt de la Cour de justice, d'ordonner sa mise en liberté immédiate et de prononcer toute mesure de substitution que le Tribunal de céans jugerait utile. Il requiert en outre l'octroi de l'assistance judiciaire. Le Ministère public du canton de Genève (ci-après: le Ministère public) a présenté des déterminations après l'échéance du délai qui lui avait été imparti. La Cour de justice se réfère aux considérants de l'arrêt attaqué et renonce à formuler des observations.