[Work in progress; this is a darn hard one to write, but I finally decided to start as triggered by a conversation with my MSR colleagues last dinner.]
This is the holy grail among all questions related to research, or any other intellectual pursuits. I used to (and still) think creativity is more of an innate talent and personality trait than something that can be taught. But I have finally gathered some anecdote to start something concrete. Some of these came from my own experiences and some from people I know. So it is a very personal perspective, and I cannot guarantee anything.
I summarize these into two main aspects, divergence and convergence. The goal is to have both in a right balance. My take is that either is hard, and the right combination is even harder.
Divergence
Many good ideas were generated by exposure to diversity, such as learning from different fields, interacting different people, and experiencing different cultures.
Examples:
(1) computer graphics is known to borrow ideas from other fields, such as physics, art, psychology, perception, architecture, interaction, etc.,
(2) a disproportional number of project ideas in Microsoft Research came from smart people talking to each other; I have heard plenty interesting stories on how an idea originated and transformed, often through multiple years and multiple folks, into a final project idea (that often bears little resemblance to the original idea, such as my SIGGRAPH 2011 paper on “non-linear revision control for images” which originated from “deformable BTF texture synthesis”),
(3) people who are multilingual and/or have been living in different countries/cultures tend to be more successful [dig out that economist(?) article].
Try to be playful and willing to take risks. Happier people tend to be more creative [dig out the source]. Those not willing to take risks usually end up with ordinary performance; this is evident in not only entrepreneurship but more mundane stuff like paper submissions: aiming for a more prestigious venue often encourages (or forces) people to be bolder.
Convergence
God/devil is in the details. Many good ideas came by carefully studying a subject. My SIGGRAPH 2011 paper on “differential domain analysis” was originated from the trigonometric transform equation which I discovered by trying to solve a puzzle of my previous SIGGRAPH 2010 paper on “multi-class blue noise sampling” (the equation first appeared on the technical report published the previous year in 2009).
Sometimes one has to be a perfectionist, pushing things beyond the very top level, to discover the golden nugget of ideas. This was the case for my SIGGRAPH 2011 paper on “discrete element textures “, which went through multiple submissions to the point that the authors started to feel desperate and only be saved by the discovery of a very important key idea (sample based representation that requires only positional but not rotational information).