All of the DNA replication machinery that operates in mitochondria is encoded in the nucleus, translated in the cytoplasm, and then transported into the mitochondrion:
"The remaining ~1500 mitochondrial proteins are encoded in the nucleus, including all proteins needed for replication and expression of the small mtDNA genome (Falkenberg et al., 2007)"
from http://ac.els-cdn.com/S0092867409012458/1-s2.0-S009286740901...
This is actually a now-standard theory of the origin of mitochondria (that they were originally separate organisms):
The relationship between them and their host cell almost seems similar to ant-fungus mutualism.