The IceCube Neutrino Observatory is a cubic-kilometer-scale neutrino detector built into the ice sheet at the geographic South Pole. Completed in December 2010, the detector consists of an array of photomultiplier tubes deployed along 86 cables ("strings") at depths of 1450 to 2450 m, as well as the IceTop air shower array of surface Cherenkov tanks. IceCube is detecting atmospheric neutrinos of energies above approximately 100 GeV at a rate of ~6 per hour, and is currently searching for extraterrestrial neutrinos from cosmic ray accelerators. A measurement of the atmospheric neutrino spectrum can be used to search for possible phenomenological signatures of quantum gravity (QG), such as violations of Lorentz invariance or quantum decoherence, and I present limits we have set on these phenomena in the neutrino sector. To extend the search for QG to much higher energies and cosmological baselines, we require an extraterrestrial neutrino source. In this context, I report on the status of our searches for neutrinos from gamma-ray bursts and from cosmic-ray interactions with the microwave background ("cosmogenic" neutrinos).