We investigate the nonlinear wave dynamics of origami-based metamaterials composed of Tachi-Miura polyhedron (TMP) unit cells. These cells exhibit strain softening behavior under compression, which can be tuned by modifying their geometrical configurations or initial folded conditions. We assemble these TMP cells into a cluster of origami-based metamaterials, and we theoretically model and numerically analyze their wave transmission mechanism under external impact. Numerical simulations show that origami-based metamaterials can provide a prototypical platform for the formation of nonlinear coherent structures in the form of rarefaction waves, which feature a tensile wavefront upon the application of compression to the system. We also demonstrate the existence of numerically exact traveling rarefaction waves. Origami-based metamaterials can be highly useful for mitigating shock waves, potentially enabling a wide variety of engineering applications.