The Fibonacci sequence is very well known, and is often explained with a story about...

Perhaps it's not an entirely practical application, but Fibonacci numbers can be used to convert from miles to kilometers and vice versa:
Take two consecutive Fibonacci numbers, for example 5 and 8. And you're done converting. No kidding – there are 8 kilometers in 5 miles. To convert back just read the result from the other end - there are 5 miles in 8 km!
But why does it work?
Fibonacci numbers have a property that the ratio of two consecutive numbers tends to the Golden ratio as numbers get bigger and bigger. The Golden ratio is a number and it happens to be approximately 1.618.
Coincidentally, there are 1.609 kilometers in a mile, which is within 0.5% of the Golden ratio.

It isn't exactly an application as such, but the upper bound of the size of a subtree in a Fibonacci heap whose root is a node with degree $k$ is $F_{k+2}$ where $F_n$ is the $n^{th}$ Fibonacci number.