How does one do PhD? I'm currently a PhD Candidate in Theoretical Physics. 

After getting into the program, I realized that studying and being able to teach Physics is one thing and doing research is another. My adviser is giving me problems and I'm working on them. 


how does he know that such a work doesn't already exist?
how does he know the problem in the first place? 
how do you search for problems to work in so that I may do the same thinking as him?
When I am working on a theoretical question/problem, I catch myself wondering, is this work really going to help others? If not, which is generally the case, what am I doing? 
When do I know, if the paper I'm working on is worth publishing?
Simply put, the answer for most of your questions is: experience.
Advisors are usually people that are working on a specific field/domain for a while. They know the other people who work on this field as well (from conferences), and their work (from doing bibliographical reviews for each written paper).

In my experience, while it is indeed interesting to work on stuff that have a direct world application, that is not strictly necessary. Pure science is still science and you never know what people will be able to do with your research in the future.