Macromolecular engineering of extracellular matrices (ECMs) in biological systems requires an understanding of the nonlinear and transient rheology and hydrodynamics, including strain stiffening and softening, yielding and fracture. ECMs, as composite hydrogels, contain not only biopolymer networks but also fibrous networks. The microstructural evolution of these networks and their interactions determine the dynamic behaviors of ECMs. However, studies exploring this relationship are scarce in literature, especially for composite hydrogels composed of biopolymer and microfibrous networks. In this work, we investigate model composite hydrogels composed of agarose networks and microfibrous chitosan networks, which are interconnected through hydrogen bonds. Under large amplitude oscillatory shear (LAOS) and startup shear flows, pure agarose hydrogels exhibit strain stiffening before brittle fracture, while pure microfibrous chitosan hydrogels exhibit strain softening. The composite hydrogels display increased stiffness while still retaining high fracture strains. Notably, the presence of microfibrous chitosan networks induces a complex stiffening-softening transition in response to LAOS and startup shear strains. To show the individual contributions of each network in the composite hydrogels, we developed a fitting model based on the linear combination of the rheological properties of agarose and microfibrous chitosan hydrogels. Using confocal rheometry, we visualize the microstructural evolution of the composite hydrogels during deformation, yielding and fracture, and reveal the underlying mechanisms of the strain stiffening-softening transition, which provides insights for future design of colloidal composite systems.