Much of QA's success (like anything else) can be tied to attitude.  Technical management can either regard QA's role in an us-vs-them contest or as a partner in building product.  Needless to say, the latter route is far more effective, though different than what is observed in most organizations.

A QA lead should be hired fairly early in the development process, soon after developers come on board.  This person should have senior hands-on experience in test design, code reviews, regression tests, etc., as they will set the QA tone for much of the development process. 

Participate in Product Design - One of the first QA tasks is to get involved with the product design as early as possible.  This accomplishes several things:  it sets the tone with QA as a development partner, it infuses high quality practices from the beginning, and it helps design for quality and testability.

Build QA Infrastructure - Another early task is build out the QA system infrastructure, as there will be little time for this later.  These systems include version control, bug tracking and especially a daily automated build and regression framework, on appropriate platforms, including ability to email test reports.  The ability to automatically build and test the product quickly will become crucial to late stage development, where subtle bugs can easily introduced.

Test Plans - Planning the tests should begin as soon as any product details are available, as writing good test plans and their subsequent tests is very time consuming.  Good test planning is fairly difficult and the subject of many other books and websites, but the big lesson is to be thorough and especially to include extra things live coverage analysis.