<>Physics theories beyond the Standard Model, like supersymmetry and models with extra dimensions, often invoke Z₂-symmetries in order to avoid new couplings that lead to unobserved new physics, like unnaturally fast proton decay. This gives rise to the possibility of heavy new particles being produced in pairs with the lightest of them being (meta-)stable. Thus, under favorable conditions, neutrinos in the PeV range can produce pairs of exotic, charged particles that can be seen in a km³-sized detector as two parallel, muon-like tracks with a track separation of a few hundred meters. This thesis discusses methods for simulating and reconstructing these exotic double tracks for the case of the IceCube neutrino observatory located at the geographic South Pole. It deals with techniques to separate them from other air shower or neutrino-induced muon events in a model independent way. The search for such events with data taken by the IceCube detector in its 79-string configuration between May 2010 and May 2011 resulted in no candidate events. This result can be used to derive limits that can be applied to explicit exotic models. As this is the first analysis of its kind, the prospects and requirements of future double track searches are also addressed.