How is a research direction determined between a graduate student and their advisor? My question applies to Science, Technology, Engineering, and Math disciplines (STEM). 

Q: By what process does a graduate student determine his or her research direction?

(Assume that the graduate student is in the first year and has no previous publications with this supervisor.)

I can imagine several scenarios:


The graduate student proposes a research topic and then their
supervisor evaluates it for originality and feasibility. In this scenario, the graduate student has the foresight to know what research directions are promising and appropriate.
The graduate student performs an extensive
literature review. In this process, the student finds a challenging and/or interesting problem. (I am not sure how much effort this requires. I also don't know how to identify a problem as "interesting" or "challenging".)
The supervisor comes up with an interesting research problem or question and then presents it to the graduate student. (This appears to be a common pattern, given the plethora of complaints that I see on-line about uninteresting research.)


I would especially like to see responses from professors who are supervisors and also from graduate students.
Any of the scenarios you describe can happen, in practice. (I am in the United States; this may differ in other countries.) It depends on the student's interests and abilities, the advisor's interests and advising style, how broad advisor's interests are, whether the advisor has funding for a particular project and needs a student to work on that problem, and many other factors.

All three have happened within my own research group. (Another possibility that happened in my research group that you haven't mentioned: student initiates a collaboration with another researcher, who proposes a topic, and involves the advisor in the project as well.)

Actually, the scenarios you describe are not discrete scenarios, but a spectrum from "most student-driven" to "most advisor-driven." Some points on the spectrum include:


Student enters grad school with a topic in mind that's judged acceptable by advisor, and proceeds with that topic. 
Student enters grad school with a topic in mind, that evolves and changes following advice from advisor.
Student enters grad school with a general idea and, together with guidance from advisor and extensive reading of literature, shapes it into a topic.
Student enters grad school without idea, advisor suggests general direction, and upon extensive reading and with guidance from advisor, student shapes it into a topic.
Advisor hands student idea, and student proceeds to execute idea. Of course, this is a PhD, so as student works on the topic, the student's mastery of the specific research will most probably come to exceed the advisor's, even though advisor originally proposed the idea.


Other scenarios include: student enters grad school with idea in mind and then changes directions completely in middle, student enters grad school with idea and changes advisors in middle but keeps idea, and many more..