A combination of experiments and Brownian Dynamics (BD) simulations is utilized to examine internal stresses in colloidal gels brought to rest from steady shear at different shear rates. A model colloidal gel with intermediate volume fraction is chosen where attractions between particles are introduced by adding non-adsorbing linear polymer chains. After flow cessation, the gel releases the stress in two distinct patterns: at high shear rates, where shear forces dominate over attractive forces, the shear-melted gel behaves as a liquid and releases stresses to zero after flow cessation. After low shear rates, though, stresses relax only partially, similar to the response of hard sphere glasses and jammed soft particles. The balance between shear and attractive forces which determines the intensity of structural distortion controls the amplitude of the residual stresses through a universal scaling. Stress decomposition to repulsive and attractive contributions in BD simulations reveals that internal stresses mainly originate from attractive forces. Moreover, analysis of particle dynamics indicates that internal stresses are associated with sub-diffusive particle displacements on average smaller than the attraction range as such short-range displacements are not sufficient to completely erase structural anisotropy caused during the course of shear.