The final inspiral of double neutron star and neutron star-black hole binaries are likely to be detected by advanced networks of ground-based gravitational wave (GW) interferometers. Maximizing the science returns from such a discovery will require the identification and localization of an electromagnetic (EM) counterpart. Here we critically evaluate and compare several possible counterparts, including short-duration gamma-ray bursts (SGRBs), "orphan" optical and radio afterglows, and ~day-long optical transients powered by the radioactive decay of heavy nuclei synthesized in the merger ejecta ("kilonovae"). We assess the promise of each counterpart in terms of four "Cardinal Virtues": detectability, high fraction, identifiability, and positional accuracy. Taking into account the search strategy for typical error regions of ~10s degs sq., we conclude that SGRBs are the most useful to confirm the cosmic origin of a few GW events, and to test the association with NS mergers. However, for the more ambitious goal of localizing and obtaining redshifts for a large sample of GW events, kilonovae are instead preferred. Off-axis optical afterglows will be detectable for at most ~10% of all events, while radio afterglows are promising only for the unique combination of energetic relativistic ejecta in a high density medium, and even then will require hundreds of hours of EVLA time per event. Our main recommendations are:(i) an all-sky gamma-ray satellite is essential for temporal coincidence detections, and for GW searches of gamma-ray triggered events; (ii) LSST should adopt a 1-day cadence follow-up strategy, ideally with ~0.5 hr per pointing to cover GW error regions (the standard 4-day cadence and depth will severely limit the probability of a unique identification); and (iii) radio searches should only focus on the relativistic case, which requires observations for a few months.