We synthesized cellulose/gypsum composites in the presence and absence of sodium alginate and investigated the interaction between the composite components as well as the mechanical properties of the final composites. Four different types of cellulose fiber materials were used: cellulose UFC100, cellulose B400, nanofibrillated cellulose, and Lyocell fiber. For all investigated composites the total amount of admixed cellulose was between 1 and 2 wt%, the amount of admixed sodium alginate was 0.5 wt%. We determined the morphology of the composites and observed that the particle and fiber dimensions of the admixed cellulose affect the mode of gypsum-gypsum interlocking and the total porosity of the composites. This in turn had a substantial influence on the mechanical properties of the final composite materials. The addition of sodium alginate resulted in an increase of ultimate strain values. Composites with Lyocell fiber, a synthetic fiber, also had a high Young's modulus.