When my kid was 6 and interested in patterns in nature, these were some of the Fibonacci resources that were a hit:

Books:

- Blockhead: The Life of Fibonacci (Joseph D'Agnese). A compelling biography.
- Growing patterns: Fibonacci numbers in nature (Sarah C. Campbell). Cool photos.

Videos:
- Doodling in Math: Spirals, Fibonacci, and Being a Plant (Vi Hart) This may be one of videos Cricket was referring to.

- Nature by Numbers (Cristobal Vila) http://www.artofproblemsolving.com/Videos/external.php?video_id=11

A nice place to start with fractals may be Nova's "Hunting the Hidden Dimension"

Spending time outside finding patterns is always a pleasure, too:)