We introduce graded Hecke algebras H based on a (possibly disconnected) complex reductive group G and a cuspidal local system L on a unipotent orbit of a Levi subgroup M of G. These generalize the graded Hecke algebras defined and investigated by Lusztig for connected G. We develop the representation theory of the algebras H. obtaining complete and canonical parametrizations of the irreducible, the irreducible tempered and the discrete series representations. All the modules are constructed in terms of perverse sheaves and equivariant homology, relying on work of Lusztig. The parameters come directly from the data (G,M,L) and they are closely related to Langlands parameters. Our main motivation for considering these graded Hecke algebras is that the space of irreducible H-representations is canonically in bijection with a certain set of logarithms of enhanced L-parameters. Therefore we expect these algebras to play a role in the local Langlands program. We will make their relation with the local Langlands correspondence, which goes via affine Hecke algebras, precise in a sequel to this paper.