Which strategy should I use to approach a problem? Sometimes I'll use $U= 1/2kx^2$ when I should use $F=-kx$ and vice versa. What are clues in a problem that would let me identify the correct approach to a given problem? And shouldn't both approaches give me the same answer in any scenario?
Obviously both are equivalent, in terms of applicability (you get the second directly by taking the gradient of the first).
My "rule of thumb" is that for simple exercices,
Of course that's only a way to choose one way to start solving a given problem; most of the time both are perfectly usable.
When going to more complicated problems however this "rule" is not necessary true ; in any case you should choose the one that gives you as little unnecessary information as possible - while still answering the question.
Force is just minus gradient of U. Gradient is just (spatial) derivative.
So, if your task has "differential" nature, it will probably suitable for force method. And if your task has "integral" nature, then it will probably suitable for potential method.