"How early can I start doing this?"

Read the book Million Dollar Consulting. It pretty much gives a step-by-step guide, from lead gen to writing proposals to how to bill by value:

http://www.amazon.com/s/ref=nb_sb_ss_c_0_19?url=search-alias...

It repeats itself a lot and is generally poorly written, but there's still a reason why it's been the top consulting book for decades.