Hyperfine interactions, magnetic interactions between the spins of electrons and nuclei, in graphene and related carbon nanostructures are studied. By using a combination of accurate first principles calculations on graphene fragments and statistical analysis, I show that both isotropic and dipolar hyperfine interactions in Sp(2) carbon nanostructures can be accurately described in terms of the local electron spin distribution and atomic structure. A complete set of parameters describing the hyperfine interactions of C-13 and other nuclear spins at substitution impurities and edge terminations is determined. These results permit the design of graphene-based nanostructures allowing for longer electron spin coherence times which are required by spintronics and quantum information processing applications. Practical recipes for minimizing hyperfine interactions in carbon nanostructures are given.