We report on the fabrication of a novel class of lightweight materials, polyimide-graphene nanocomposites (0.01-5 vol %), with tunable electrical conductivity. The graphene-polyimide nanocomposites exhibit an ultra-low graphene percolation threshold of 0.03 vol % and maximum dc conductivity of 0.94 S/cm, which we attribute to excellent dispersion, extraordinary electron transport in the well-dispersed graphene, high number density of graphene nanosheets, and the π-π interactions between the aromatic moieties of the polyimide and the carbon rings in graphene. The dc conductivity data are shown to follow the power-law dependence on the graphene volume fraction near the percolation threshold. The ac conductivity of the nanocomposites is accurately represented by the extended pair-approximation model. The exponent s of the approximation is estimated to be 0.45-0.61, indicating anomalous diffusion of charge particles and a fractal structure for the conducting phase, lending support to the percolation model. Low-temperature dc conductivity of the nanocomposites is well-approximated by the thermal fluctuation-induced tunneling. Wide-angle X-ray scattering and transmission electron microscopy were utilized to correlate the morphology with the electrical conductivity. The lack of maxima in X-ray indicates the loss of structural registry and short-range ordering.