Closely related to Zev's answer is that if $p$ is a prime not equal to $2$ or $5$, then $F_p \equiv \left( \frac{p}{5} \right) \bmod p$. The Fibonacci numbers also have a special relationship to continued fractions related to the second part of Nurdin's answer which I wrote an old blog post about here. There's a lot to say about them, so I wish you'd be a little more specific!
Edit: For example, one of my favorite Fibonacci exercises (which is somewhere in Stanley) is to write down the generating function for $\sum_{n \ge 0} F_{n+1}^2 x^n$ with no computation, using the fact that $F_{n+1}$ is the number of ways to tile a board of length $n$ with tiles of length $1$ and $2$, interpreting $F_{n+1}^2$ as the number of pairs of such tilings, and determining the "prime" tilings that can occur (the fancy keyword here is "monoid factorization").
Edit #2: While I'm on a combinatorics bent, there is another relationship between the Fibonacci numbers and continued fractions, but this time of power series. The generating function for the Catalan numbers can be described as a continued fraction corresponding to a recursive definition of ordered rooted trees, and one of the "convergents" of this power series is the generating function for the even Fibonacci numbers, which "explains" why the even Fibonacci numbers approximate the Catalan numbers. I also wrote a blog post about this here. There's a lot of interesting stuff here, although I'm not sure how to convert it into a good problem.
