We use measurements of the HI content, stellar mass and star formation rates in ~190 massive galaxies with stellar masses greater than 10^10 Msun, obtained from the Galex Arecibo SDSS Survey (GASS) described in Paper I (Catinella et al. 2010) to explore the global scaling relations associated with the bin-averaged ratio of the star formation rate over the HI mass, which we call the HI-based star formation efficiency (SFE). Unlike the mean specific star formation rate, which decreases with stellar mass and stellar mass surface density, the star formation efficiency remains relatively constant across the sample with a value close to SFE = 10^-9.5 yr^-1 (or an equivalent gas consumption timescale of ~3 Gyr). Specifically, we find little variation in SFE with stellar mass, stellar mass surface density, NUV-r color and concentration. We interpret these results as an indication that external processes or feedback mechanisms that control the gas supply are important for regulating star formation in massive galaxies. An investigation into the detailed distribution of SFEs reveals that approximately 5% of the sample shows high efficiencies with SFE > 10^-9 yr^-1, and we suggest that this is very likely due to a deficiency of cold gas rather than an excess star formation rate. Conversely, we also find a similar fraction of galaxies that appear to be gas-rich for their given specific star-formation rate, although these galaxies show both a higher than average gas fraction and lower than average specific star formation rate. Both of these populations are plausible candidates for "transition" galaxies, showing potential for a change (either decrease or increase) in their specific star formation rate in the near future. We also find that 36+/-5% of the total HI mass density and 47+/-5% of the total SFR density is found in galaxies with stellar mass greater than 10^10 Msun. [abridged]