A future galactic SN can be located several hours before the optical
explosion through the MeV-neutrino burst, exploiting the directionality of
$\nu$-$e$-scattering in a water Cherenkov detector such as Super-Kamiokande. We
study the statistical efficiency of different methods for extracting the SN
direction and identify a simple approach that is nearly optimal, yet
independent of the exact SN neutrino spectra. We use this method to quantify
the increase in the pointing accuracy by the addition of gadolinium to water,
which tags neutrons from the inverse beta decay background. We also study the
dependence of the pointing accuracy on neutrino mixing scenarios and initial
spectra. We find that in the ``worst case'' scenario the pointing accuracy is
$8^\circ$ at 95% C.L. in the absence of tagging, which improves to $3^\circ$
with a tagging efficiency of 95%. At a megaton detector, this accuracy can be
as good as $0.6^\circ$. A TeV-neutrino burst is also expected to be emitted
contemporaneously with the SN optical explosion, which may locate the SN to
within a few tenths of a degree at a future km$^2$ high-energy neutrino
telescope. If the SN is not seen in the electromagnetic spectrum, locating it
in the sky through neutrinos is crucial for identifying the Earth matter
effects on SN neutrino oscillations.