Each of these factors will dictate which methodology is most appropriate for your research questions. We'll go into each of these factors in more detail.
Whether you are just starting out and wanting to get an idea of what problems may exist, the first factor to consider is if you already have an understanding of the problems users are facing. Based on the information you have about the problem, there may be a need to understand its severity or frequency relative to other known problems.
If you're in the initial discovery phase, it's important to be able to get into the weeds of your problem. You'll want the ability to ask detailed questions, follow up on participants' answers, and deviate from your discussion guide when interesting tangents present themselves. Thus, in-depth interviews are likely going to be preferable rather than a survey or other method where you have a fixed set of questions and no ability to follow up.
Once you have an idea of the types of issues your users are experiencing, you may want to understand how prevalent those issues are with the wider population. To do that, you need a suitably large sample of users so that you can be reasonably confident that your findings are representative of the user population as a whole. In this instance, a survey that you can distribute to potentially hundreds or thousands of users is a better fit. Using a survey with a fixed set of answer choices will allow for easy analysis of even a large number of responses.
The next thing you'll want to think about when devising your study is the characteristics of your users' behavior or specific actions you're looking to study. Do all people perform a certain behavior in the same way, or does it vary, perhaps based on their role? Take for example administrators versus regular users. Their understanding and usage of the product will likely be very different. In that case, you would want to be sure you recruit people in different roles.
Does usage change over time? Perhaps you're interested in studying how people learn to use a new feature. It might be a good idea to talk to users at multiple intervals as they learn the feature, or at least recruit users at different points on the spectrum of usage.
The important thing is to think about how usage might be different for people based on who they are or how they're using your product and try to recruit people that reflect that different usage.
People often ask at what stage of product development they should be conducting UX research. The reality is that you can conduct research at every stage of development with different levels of detail. The fidelity of research insights follows the fidelity of design.
If you have a hand drawn product flow on some pieces of paper, you can put that in front of users and get a basic, high level idea of how they comprehend the experience. The key phrase being high level, you won't get any detail and you shouldn't try. If you then turn that flow into a high fidelity prototype where users can click hotspots on a series of screen images to progress through the flow, you can get more detail, but still not as much as if they were interacting with a production interface.
The important thing to keep in mind is that you can do research at every stage of the development lifecycle, as long as you remain mindful of the limitations of what you can learn. However, even with these limitations, doing research at early stages is immensely valuable for providing product direction. Some information is so much better than no information.