In supersymmetric theories where the lightest supersymmetric particle is the gravitino the next to lightest supersymmetric particle is typically a long lived charged slepton. In this paper, following our earlier proposal, we perform a detailed study of the production of pairs of these particles induced by the interactions of high energy cosmic neutrinos with nucleons in the earth, their propagation through the earth and finally their detection in neutrino telescopes. We investigate the charged slepton energy loss in detail and establish that the relatively small cross-section for the production of supersymmetric particles is partially compensated for by the very long range of these heavy particles. The signal, consisting of two parallel charged tracks emerging from the earth, is characterized by a track separation of a few hundred meters. We perform a careful analysis of the main background, coming from direct di-muon production, and show that it can be separated from the signal due to its characteristically smaller track separation. We conclude that neutrino telescopes will complement collider searches in the determination of the supersymmetry breaking scale, and may even provide the first evidence for supersymmetry at the weak scale.