The study describes a comprehensive methodology to evaluate X-Ray micro-computed tomography data from sand samples and to characterize their 3D microstructural properties. Fine and medium-grained sands are analyzed in their natural and bio-cemented states. While the two materials exhibit similar peak and residual strengths in their untreated state, they yield distinctly different strength improvements in their bio-cemented state, despite similar cementation contents. To understand the underlying mechanisms that govern this behavior, a recently developed approach is presented to gain new insights into the specimen's micro-architecture. Results capture a series of properties such as the volume distribution of pore bodies, pore throats, particles, interparticle contacts, precipitation bonds, and distribution of tortuous paths. It is found that the intrinsic, i.e., pre-cementation microstructural properties, are crucial in determining the spatial distribution of post-cementation bonds. Furthermore, the volume of bonds at interparticle contacts and in throats governs the overall contact area, directly reflecting interparticle stress transmission. Contact area increases by 180% for the medium-grained sand compared to 120% for the fine-grained. Overall, the methodology introduced in this study forms a new basis for understanding biocementation and can contribute to a more robust formulation of simulation models incorporating pore and contact mechanics in porous media.