We directly measure the hole spin lifetime in ferromagnetic GaMnAs via time- and polarization-resolved spectroscopy. Below the Curie temperature Tc, an ultrafast photoexcitation with linearly-polarized light is shown to create a non-equilibrium hole spin population via the dynamical polarization of holes through p-d exchange scattering with ferromagnetically-ordered Mn spins, and we characterize their relaxation dynamics. The observed relaxation consists of a distinct three-step recovery : (i) femtosecond (fs) hole spin relaxation ~ $160-200 fs, (ii) picosecond (ps) hole energy relaxation ~ 1-2 ps, and (iii) a coherent, damped Mn spin precession with a period of ~ 250 ps. The transient amplitude of the hole spin component diminishes with increasing temperature, directly following the ferromagnetic order, while the hole energy amplitude shows negligible temperature change, consistent with our interpretation. Our results thus establish the hole spin lifetimes in ferromagnetic semiconductors and demonstrate a novel spectroscopy method for studying non-equilibrium hole spins in the presence of correlation and magnetic order.