Broadly speaking, declarative programming concerns itself with telling the computer what to do. Imperative programming concerns itself with telling the computer how to do it. Any non-trivial program will necessarily contain both.
Imperative programming is typically associated with control flow, loops and mutable state. Programs written in the procedural paradigm are typically imperative, though they don't necessarily have to be; you can write functions in a procedural language that operate in much the same way that they do in a functional language.
Imperative programming begins at the machine language level, where loops, jumps and state are common. From there, you can create higher abstractions by writing programming languages, starting from assembly language (which, for the most part, maps to processor instructions). You can progress to a procedural language like C, make it object-oriented (C with classes), add a lot more sophistication (C++), and still be entrenched in imperative programming for the most part.
Declarative programming is characterized more by declarations than instructions. It encompasses domain-specific languages like SQL, functional languages like Haskell, and declarative data structures like XML. Purely functional programming languages dispense with mutable state, preferring to store state in the spaces between function calls, rather than as private members of a class. You can write purely functional code in an imperative/OO language, as Linq demonstrates.
The reason you see recursion a lot in purely functional languages is because those language also dispense with loops. Without a loop (a construct that is grounded specifically in the how), one must resort to recursion to get loop-like behavior. As you have already discovered, many problems can be expressed naturally using recursion, once you understand it.
The important thing to remember about thinking declaratively is that it's just another level of abstraction. Should your students think about solving problems declaratively? Absolutely, but they must also be capable of telling the computer how to solve the problem, not just what.
It's no accident that the programming languages that are considered most practical and pragmatic by their practicioners are the ones that you can write code in both declarative and imperative styles.
