RR Lyrae stars may be the best practical tracers of Galactic halo (sub-)structure and kinematics. The PanSTARRS1 (PS1) $3\pi$ survey offers multi-band, multi-epoch, precise photometry across much of the sky, but a robust identification of RR Lyrae stars in this data set poses a challenge, given PS1's sparse, asynchronous multi-band light curves ($\lesssim 12$ epochs in each of five bands, taken over a 4.5-year period). We present a novel template fitting technique that uses well-defined and physically motivated multi-band light curves of RR Lyrae stars, and demonstrate that we get accurate period estimates, precise to 2~sec in $>80\%$ of cases. We augment these light curve fits with other {\em features} from photometric time-series and provide them to progressively more detailed machine-learned classification models. From these models we are able to select the widest ($3/4$ of the sky) and deepest (reaching 120 kpc) sample of RR Lyrae stars to date. The PS1 sample of $\sim 45,000$ RRab stars is pure (90\%), and complete (80\% at 80 kpc) at high galactic latitudes. It also provides distances precise to 3\%, measured with newly derived period-luminosity relations for optical/near-infrared PS1 bands. With the addition of proper motions from {\em Gaia} and radial velocity measurements from multi-object spectroscopic surveys, we expect the PS1 sample of RR Lyrae stars to become the premier source for studying the structure, kinematics, and the gravitational potential of the Galactic halo. The techniques presented in this study should translate well to other sparse, multi-band data sets, such as those produced by the Dark Energy Survey and the upcoming Large Synoptic Survey Telescope Galactic plane sub-survey.