We present the results of numerical calculations on propagation of Extremely-high energy (EHE) neutrinos and charged leptons in the earth for trajectories in all phase space of nadir angles. Our comprehensive calculation has shown that not only the secondary produced muons but also taus survive without decaying in energy range of 10PeV-100PeV with intensity approximately three orders of magnitude lower than the neutrino flux regardless of EHE neutrino production models. They form detectable horizontal or downgoing events in a 1km$^3$ underground neutrino telescope such as the IceCube detector. The event rate and the resultant detectability of EHE signals in comparison with the atmospheric muon background are also evaluated. The 90 % C.L. upperlimit of EHE neutrino fluxes by a km$^2$ detection area would be placed at $E^2dF/dE \simeq 3.7\times 10^{-8}$ GeV/cm$^2$ sec sr for $\nu_{\mu}$ and $4.6\times 10^{-8}$ for $\nu_{\tau}$ with energies of $10^9$ GeV in absence of signals with energy-loss in a detection volume of 10PeV or greater.