We introduce the GALEX Arecibo SDSS Survey (GASS), an on-going large program that is gathering high quality HI-line spectra using the Arecibo radio telescope for an unbiased sample of ~1000 galaxies with stellar masses greater than 10^10 Msun and redshifts 0.025<z<0.05, selected from the SDSS spectroscopic and GALEX imaging surveys. The galaxies are observed until detected or until a low gas mass fraction limit (1.5-5%) is reached. This paper presents the first Data Release, consisting of ~20% of the final GASS sample. We use this data set to explore the main scaling relations of HI gas fraction with galaxy structure and NUV-r colour. A large fraction (~60%) of the galaxies in our sample are detected in HI. We find that the atomic gas fraction decreases strongly with stellar mass, stellar surface mass density and NUV-r colour, but is only weakly correlated with galaxy bulge-to-disk ratio (as measured by the concentration index of the r-band light). We also find that the fraction of galaxies with significant (more than a few percent) HI decreases sharply above a characteristic stellar surface mass density of 10^8.5 Msun kpc^-2. The fraction of gas-rich galaxies decreases much more smoothly with stellar mass. One of the key goals of GASS is to identify and quantify the incidence of galaxies that are transitioning between the blue, star-forming cloud and the red sequence of passively-evolving galaxies. Likely transition candidates can be identified as outliers from the mean scaling relations between gas fraction and other galaxy properties. [abridged]