I have been trying to improve my problem solving skills and I have some experience to share. When I read an IMO type of question, there are three stages for me.
1. I freeze after reading the problem. It takes a while to understand the problem (not always but most of the time). I believe that cognitive ability (measure of which is IQ) plays a major role here. It is just a matter of time. If you stare at it for a while, it will sink in. Certain heuristics given in Polya's book help in getting a grip on the mathematical situation given in the problem.
2. If I managed to cross the first phase, then the second phase is to figure out what can be done to solve the problem. A proof is basically a chain of implications. A=>B=>C=D, A, B, C, and D being mathematical statements. It can be more complicated like (A&B)=>(C OR E) => D. The tricky thing about really hard problems is that while statement A would be given, they say nothing about statements B, C and E. We will need to show that D is true. So based on experience, B, C, and E have to be "figured out". More obscure these intermediate statements, harder the problem. If these intermediate steps are more in number, then the problem gets exponentially harder.
These intermediate steps are the ones Paul Zeitz refers to as the "crux moves".
Here too, better cognitive skills will help. I feel that it is not as crucial here as in #1 because once I cross the stage mentioned in #1, then it is a matter of working hard to figure out potential candidates for statements B, C and E. For me, being creative and coming up with more number of potential crux moves is easier than the first stage which often happens to be a big problem. Nevertheless, this stage of problem solving is not trivial at all. This is perhaps 70 on a scale where step #1 is 100.
Metacognition is what is needed in this stage. You can read Alan Schoenfeld's "Mathematical Problem Solving" for more details. Having good control of "direction of thinking" is extremely important for this stage and the final stage of problem solving.
3. This step is the final step in solving the problem. I feel that this stage is almost as hard as #1. I do manage to come up with humongous number of potential crux moves. But IMO problems are very difficult because seeing the crux move is very very hard. Most of the times, after seeing the crux move, proving them might be hard too but is a problem of lesser magnitude.
I have solved some problems from the IMO (only 1s and 4s). Lack of intelligence can be made up by practicing a lot of problems. That way, getting through stage #1 will become easier if there is good familiarity with the mathematical situation that is given in the problem. Also, practice helps in gaining good control in using tools (like recognizing the auxiliary construction in geometry, or looking for something that is a constant or a mono-variant etc). Stage #3 is subject to the creativity that I have in the area on which the problem is given.
Quite honestly, I believe that intense practicing "in the right direction" can get you through IMO even with moderate IQ. But I needed a tonne of practice to solve a meager number of IMO problems.
I may not have added much here to what others have said but thought I will share my experience. Basically IMO requires intense training and also guidance from someone who knows. IQ is needed to a good extent but given that many of the medalists start out from nowhere, it must be possible to get to IMO bronze medal level with intense training. One thing to keep in mind is that good meta-cognitive skills are needed on top of good intelligence. Changing direction of thought based on the fact that current approach is not working is very critical. I used to simply keep trying one approach and not back off inspite of knowing that it is not working. I can now (after a lot of practice) try a lot of directions in order to solve a problem.