Faits: A. Par ordonnance pénale du 21 juin 2011, A._, ressortissant roumain, a été condamné pour cambriolage à 60 jours-amende, sous déduction d'un jour-amende correspondant à un jour de détention avant jugement, le montant du jour-amende étant fixé à 30 francs et le bénéfice du sursis lui étant accordé pendant trois ans. Cette ordonnance, contestée, a été transmise au Tribunal pénal du canton de Genève. B. 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. Par ordonnance du 20 octobre 2011, le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné la détention provisoire du prénommé pour une durée initiale courant jusqu'au 30 novembre 2011, en raison d'un risque de collusion et de fuite (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. La formule de jonction se trouve deux feuillets après ladite page de garde. Le 1er décembre 2011, le Tmc a rendu une ordonnance de prolongation de la détention provisoire, en raison des risques de collusion et de fuite, dans la cause P/12264/2011. Statuant sur recours de l'intéressé, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a confirmé cette ordonnance par arrêt du 22 décembre 2011. Elle a considéré en substance que les charges étaient suffisantes, qu'il existait des risques de fuite et de collusion, qu'aucune mesure de substitution n'était à même de pallier. Elle a également relevé que la jonction des procédures P/12264/2011 et P/14657/2011 pouvait être rendue selon un formalisme limité. C. 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 conclut au rejet du recours. La Cour de justice se réfère aux considérants de l'arrêt attaqué et renonce à formuler des observations. Le recourant a répliqué par courrier du 2 février 2012.