Since your question is very broad, here is a somewhat broad answer: Read about problem posing.
Three key pieces are:
Silver, E. A. (1994). On Mathematical Problem Posing. For the learning of mathematics, 14(1), 19-28.
and the book
Brown, S. I., & Walter, M. I. (2005). The art of problem posing. Psychology Press.
The latter is a re-print of a book that first came out in 1983. You can also find a related book edited by Brown and Walter; a citation for the most recent version is:
Brown, S. I., & Walter, M. I. (Eds.). (2014). Problem posing: Reflections and applications. Psychology Press.
Start with these three documents, their references, and (searching on google scholar) other papers and articles that cited them.
To sketch out very roughly Brown and Walter's suggestion: Start with a mathematical scenario, list assumptions, vary constraints (in their terms: "What-if-not-ing"), and then ask questions. You can even "cycle" through this process repeatedly in order to produce problems of increasing complexity.
Of course, problem posing brings with it the danger of not knowing the answer to what you are asking.
For example, your starting scenario might use the Pythagorean Theorem:
Find all integer solutions for $x^2 + y^2 = z^2$.
This particular example is explored in Brown and Walter's book, but it seems to me a reasonable assumption to list is that the exponent everywhere is $2$, and to ask for integer solutions when the exponent is $3$.... or, if one feels particularly daring, to generalize and ask for exponent $k \geq 3$.
At a glance, this might seem like a reasonable question; but, if you are familiar with Fermat's Last Theorem, then you will realize that this is not an appropriate problem for most students.
You can find some of my brief remarks about problem posing and creativity in part $4b$ here, and a couple of other examples relating problem posing and intuition in the concrete example section here.
A final remark: You start off by mentioning the "essential" role of problem solving in enhancing our understanding of mathematics. It may be worth noting that problem posing plays an important role in solving; consider Polya's list of heuristics and how many of them are questions: What's a related problem? What's a simpler problem? How can I generalize this problem? Etc. (Historically, both Silver, in the first piece cited above, and Kilpatrick, on problem formulation, trace this observation, i.e., that problem posing is an integral part of problem solving, at least back to a 1945 paper by Karl Duncker.)
As Cantor (1867) wrote in his doctoral thesis:
“In re mathematica ars proponendi pluris facienda est quam solvendi”
(“In mathematics the art of asking questions is more valuable than solving problems”).