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