Edit (5/24/14): For the reader interested in a somewhat longer answer, I am including the literature review (and all references) from my thesis on conceptions of creativity with regard to problems posed from the multiplication table. A copy of the excerpt can be found here. My original, shorter answer remains un-edited below.
The story of mathematical creativity is long and probably deserves an entire book dedicated to it.
One (perhaps subtle) difficulty is that it's tough to define what is meant by creativity. For example, in
Treffinger, D. J., Young, G. C., Selby, E. C., & Shepardson, C. (2002). Assessing Creativity: A Guide for Educators. National Research Center on the Gifted and Talented.
the authors write:
Treffinger (1996) reviewed and presented more than 100 different definitions from the
literature. Aleinikov, Kackmeister, and Koenig (2000) offered 101 contemporary
definitions from children and adults (p. 5).
Furthermore, there is a debate about whether or not creativity is domain-specific (i.e., whether one can be generally creative or whether one should instead use words like mathematically creative).
Rather than attempt to review the creativity literature in its entirety, let me hit a few high points:
$1.$ Creativity research did not take off until about 1950, when the president of the APA, J.P. Guilford, gave his inaugural address (aptly) titled Creativity, in which he called for the concept to be investigated - primarily in terms of various traits.
$2.$ Preceding Guilford's address, related work came from the literature on thought. Wallas' (1926) book The Art of Thought is the first to put forth the five-stage model of problem solving: preparation, incubation, intimation, illumination, and verification.
$3a.$ There are numerous descriptions of mathematical creativity that accord with the incubation model described by Wallas. The most famous example is Poincare stepping onto an omnibus and having a revelation about Fuschian functions; this is contained in his work The Foundations of Science in a chapter (again, aptly) titled Mathematical Creation. This book, and that chapter in particular, encouraged another mathematician to write his own book on mathematical creativity: Jacques Hadamard's The psychology of invention in the mathematical field. (This is all suggested reading!)
$3b.$ For other examples, see Cohen's write-up of his development of forcing (related to my MO answer here) or Gauss' comment about post-incubation illumination, cited in Klamkin's (1994) Mathematical Creativity in Problem Solving and Problem Proposing II as recorded by K. Knopp:
...all the brooding, all the searching was for nothing; finally, a few days ago I succeeded. But not by long searches but by the sheer grace of God, I may say, like lightning strikes, the riddle was solved; I myself would not be able to find the connection between what I knew previously, with what I used for my last attempt and with what finally succeeded.
The lesson of $3a$ and $3b$ is that even great mathematicians are (often) metacognitively unaware as to what produced their final creative insight. What's clear, though, is that before the incubation period, one needs to work consciously on a problem (Wallas' first stage). To quote Poincare:
There is another remark to be made about the conditions of... unconscious work: it is possible, and of a certainty it is only fruitful, if it is on the one hand preceded and on the other hand followed by a period of conscious work... Perhaps we ought to seek the explanation in the preliminary period of conscious work which always precedes all fruitful unconscious labor.
In a related vein, George Polya writes (semi-humorously):
Past ages regarded a sudden good idea as an inspiration, a gift from the gods. You must deserve such a gift by work, or at least a fervent wish.
(For a very outdated and, in my opinion, poorly written article that also emphasizes work, see Adler's (1984) Mathematics and Creativity in Mathematics, People, Problems, Results v2.)
$4a.$ Your question asks: "How can educators encourage creativity without sacrificing correctness?" I think the key is to conceive of creativity as produced by conscious work. One account in the creativity literature to this end is provided by Howard Gruber; see his book Darwin on Man, or compare the Gauss quotation above (with the frequently used metaphor of lightning) to the excerpt here. Much of Gruber's work helps to demystify creativity; to this end, helping students see that even great theoretical advances are a product of hard work and not some magical power can encourage innovation and creativity.
$4b.$ For a concrete suggestion as to how educators can encourage creativity, I would suggest incorporating problem posing (not just problem solving) into the classroom. This relates to creativity and the literature on problem finding; you can find a more extended discussion on the relation between the two in the section Problem posing as a feature of creative activity or exceptional mathematical ability in:
Silver, E. A. (1994). On Mathematical Problem Posing. For the learning of mathematics, 14(1), 19-28.
Sources relating the above work to creativity can be found here, e.g.,
Silver, E. A. (1997). Fostering creativity through instruction rich in mathematical problem solving and problem posing. ZDM, 29(3), 75-80.
Finally, as far as problem posing, the classic text is Brown and Walter's "The Art of Problem Posing," which provides a very accessible account of how to begin with a given mathematical scenario and use it to pose increasingly complex problems, as well as how this can be incorporated into an actual course.
