This Letter presents a theoretical investigation of ultrafast spin-dependent carrier dynamics in semiconductors due to strong spin-orbit coupling using holes in bulk GaAs as a model system. By computing the microscopic carrier dynamics in the anisotropic hole-band structure including spin-orbit coupling, we obtain spin-relaxation times in quantitative agreement with measured hole-spin relaxation times [Phys. Rev. Lett. 89, 146601 (2002)10.1103/PhysRevLett.89.146601]. We show that different optical techniques for the measurement of hole-spin dynamics yield different results, in contrast to the case of electron-spin dynamics.