For me, the process is as follows:
- Do the exercise.
- Do the exercise again. This is probably faster than the first time, since I have a vague feeling of what I should be doing, and maybe remember some dead ends that I can avoid.
- Repeat step number 2. At some point, if I have to do the exercise often enough, I learn it by heart. This is rare.
In practice, this rarely happens unless I am teaching and encounter the problem often there, or I do research on a given subject and have to think through the same lemma several times.
Instead, the problem solving heuristics and patterns of thought that are repeated often are what stick to mind. When encountering a familiar problem, a problem of familiar type, I have a feel for the problem and know which common technique to try first, and I know what the likely steps in solving the problem are. I still have to do the work to be sure the attempted proof works (unless I have done the same argument several times recently).
It is, in general, okay to not remember solutions by heart. If you can repeat the argument, even if it feels like fumbling, that is already good.
The most elementary context in which I can observe this is multiplication; say, the powers of two. How much is $2^7$? I can remember $2^6 = 64$ (because I have calculated this so frequently) so $2^7 = 128$. If I want to be sure this is the right answer, I have to check it. If I do this calculation often enough, then I can guess the right answer immediately, but must still check it to be certain. Before I remembered $2^6$, I had to start with $2^5 = 32$, and before that, I had to start from $2^3$, and so on.
A similar process happens with less elementary problems, though the steps that happen by heart or from strong intuition are more interesting.