We present the design, methods, and first results of the MUSE Analysis of Gas around Galaxies (MAGG) survey, a large programme on the Multi Unit Spectroscopic Explorer (MUSE) instrument at the Very Large Telescope (VLT) which targets 28 z > 3.2 quasars to investigate the connection between optically-thick gas and galaxies at z~3-4. MAGG maps the environment of 52 strong absorption line systems at z > 3, providing the first statistical sample of galaxies associated with gas-rich structures in the early Universe. In this paper, we study the galaxy population around a very metal poor gas cloud at z~3.5 towards the quasar J124957.23-015928.8. We detect three Lyman alpha emitters within <200km/s of the cloud redshift, at projected separations <185 kpc (physical). The presence of star-forming galaxies near a very metal-poor cloud indicates that metal enrichment is still spatially inhomogeneous at this redshift. Based on its very low metallicity and the presence of nearby galaxies, we propose that the most likely scenario for this LLS is that it lies within a filament which may be accreting onto a nearby galaxy. Taken together with the small number of other LLSs studied with MUSE, the observations to date show a range of different environments near strong absorption systems. The full MAGG survey will significantly expand this sample and enable a statistical analysis of the link between gas and galaxies to pin down the origin of these diverse environments at z~3-4.