Experiments over many decades are suggestive that the combination of cellular contractility and active phase separation in cell-matrix composites can enable spatiotemporal patterning in multicellular tissues across scales. To characterize these phenomena, we provide a general theory that incorporates active cellular contractility into the classical Cahn-Hilliard-Larché model for phase separation in passive viscoelastic solids. Within this framework, we show how a homogeneous cell-matrix mixture can be destabilized by activity via either a pitchfork or Hopf bifurcation, resulting in stable phase separation and/or traveling waves. Numerical simulations of the full equations allow us to track the evolution of the resulting self-organized patterns in periodic and mechanically constrained domains, and in different geometries. Altogether, our study underscores the importance of integrating both cellular activity and mechanical phase separation in understanding patterning in soft, active biosolids in both in vivo and in vitro settings.