The objective of this investigation was to find a suitable methodology to disperse and mix two different types of cellulose-based materials, microcrystalline cellulose (MCC) and nano-fibrillated cellulose (NFC), into cement pastes. To achieve this, six different dispersion strategies were explored, including mechanical means, i.e., mechanical and magnetic stirring, ultrasonication, and chemical methods, i.e., addition of polaxamer and superplasticizer, and TEMPO oxidation. Their dispersion capacity and mixture feasibility were assessed using flow table and compression tests. Then the selected methods were applied to each type of fiber to enhance the resulting flexural properties at the optimal fiber content. Both MCC and NFC were characterized in terms of morphology by means of light microscopy (LM), transmission electron microscopy (TEM), and scanning electron microscopy (SEM), in addition to the water retention value. The reinforcement characteristics and the microstructure of the composites were correlated with their mechanical performance using thermo-gravimetric analysis and porosity evaluation. Ultrasonication and the use of superplasticizer were found to be the most suitable for MCC and NFC, respectively. The optimal content of MCC was 0.75% by wt., and that of NFC was 1% by wt. These mixtures resulted in increases in both strength and flexural modulus by more than 5 and 8 times, for MCC and by more than 3 and 7 times for NFC, respectively. The analyses indicated that the enhanced response on NFC addition is probably associated with its intrinsic properties and bridging capacity, and for the inclusion of MCC the filler effect may have also influenced the mechanical behavior.