**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.

<sub>NOAD</sub>