fateFate is from the latinLatin fatum
fatum, which means "that which has been spoken."
that which has been spokenDestiny
destiny is from the Latin destinare
destinare, which means to make firm"to make firm" or to establish"to establish."
I agree with Billare that fatefate has a more fatalistic feel (fatalistic also comes from `fatum'fatum), as it has a deeper implication of one's end being decided by a separate entity.
NOADReference: the NOAD.