How long do PhD students typically take to come up with their research proposal?
If you are talking about the writing of a formal proposal document, the rules vary from department to department. If you are talking about the idea for a project, then that needs to be developed very early on—the tentative idea should already be in place by the time work starts. 

In my department, for instance, students had roughly one year from the completion of the qualifying examination to submit the research proposal. This was a fairly substantial document (25-30 pages). Other schools I considered required the submission as late as the third or fourth year (in what was nominally a five- to six-year program); in that case, the research proposal was almost a first draft of the thesis, as it was typically anywhere from 50 to 100 pages in length!

In my current department, students receive fellowships to work on projects with their advisors. In such cases, the advisor typically plans the basic outline of the project, and the start of the work plan. Later years are left for the student to devise.