Old English toð (plural teð), from Proto-Germanic *tanthu- (source also of Old Saxon, Danish, Swedish, Dutch tand, Old Norse tönn, Old Frisian toth, Old High German zand, German Zahn, Gothic tunþus), from PIE root *dent- "tooth." Plural teeth is an instance of i-mutation.
The loss of -n- before spirants is regular in Old English, Old Frisian, and Old Saxon: compare goose (n.), five. Also thought, from stem of think; couth from the stem of can (v.1); us from *uns.
Application to tooth-like parts of other objects (saws, combs, etc.) first recorded 1520s. Tooth and nail as weapons is from 1530s. The tooth-fairy is attested from 1964.