The realization of graphene-gold-nanoparticle (G-AuNP) hybrids is presented here through a versatile electrochemical approach, which allows the continuous tuning of the size and density of the particles obtainable on the graphene surface. Raman scattering from graphene, which is significantly enhanced in such hybrids, is systematically investigated as a function of the size and density of particles at the same location. In agreement with theory, it is shown that the Raman enhancement is tunable by varying predominantly the density of the nanoparticles. Furthermore, it is observed that the increase in Raman cross-section and the strength of Raman enhancement varies as a function of the frequency of the vibrational mode, which may be correlated with the plasmonic fingerprint of the deposited AuNPs. In addition to this electromagnetic enhancement, support is found for a chemical contribution through the occurrence of charge transfer from the AuNPs onto graphene. Finally, G-AuNP hybrids can be efficiently utilized as SERS substrates for the detection of specifically bound non-resonant molecules, whose vibrational modes can be unambiguously identified. With the possibility to tune the degree of Raman enhancement, this is a platform to design and engineer SERS substrates to optimize the detection of trace levels of analyte molecules.