When would be a good time to ask a professor if he will consider being my PhD advisor? I just started working with this professor, I am beginning to really like the work they are doing in his lab. When do you  think I should ask him if I can do a PhD under his tutelage?
I would tell the professor that you're interested right away, but don't necessarily expect him/her to say yes or no immediately.  Rather than saying "would you advise my Ph.D. research?", just say, "I'm planning to do a Ph.D. and I'm interested in working under your supervision."

You'll probably get a "let's see how this first project turns out", but it will be easier to discuss in the future and the professor will know you are interested.