A new 7-beam 6-7 GHz receiver has been built to survey the Galaxy and the Magellanic Clouds for newly forming high-mass stars that are pinpointed by strong methanol maser emission at 6668 MHz. The receiver was jointly constructed by Jodrell Bank Observatory (JBO) and the Australia Telescope National Facility (ATNF) and allows simultaneous coverage at 6668 and 6035 MHz. It was successfully commissioned at Parkes in January 2006 and is now being used to conduct the Parkes-Jodrell multibeam maser survey of the Milky Way. This will be the first systematic survey of the entire Galactic plane for masers of not only 6668-MHz methanol, but also 6035-MHz excited-state hydroxyl. The survey is two orders of magnitude faster than most previous systematic surveys and has an rms noise level of ~0.17 Jy.This paper describes the observational strategy, techniques and reduction procedures of the Galactic and Magellanic Cloud surveys, together with deeper, pointed, follow-up observations and complementary observations with other instruments. It also includes an estimate of the survey detection efficiency. The 111 days of observations with the Parkes telescope have so far yielded >800 methanol sources, of which ~350 are new discoveries. The whole project will provide the first comprehensive Galaxy-wide catalogue of 6668-MHz and 6035-MHz masers.