We study tetrahedron maps, which are set-theoretical solutions to the Zamolodchikov tetrahedron equation, and Yang-Baxter maps, which are set-theoretical solutions to the quantum Yang-Baxter equation. In particular, we clarify the structure of the nonlinear algebraic relations which define linear (parametric) tetrahedron maps (with nonlinear dependence on parameters), and we present several transformations which allow one to obtain new such maps from known ones. Furthermore, we prove that the differential of a (nonlinear) tetrahedron map on a manifold is a tetrahedron map as well. Similar results on the differentials of Yang-Baxter and entwining Yang-Baxter maps are also presented. Using the obtained general results, we construct new ex...