The key for me has always been to help the company understand savings of doing things right the first time over the cost of redoing things or dealing with a catastrophic problem. It works best for me when I approach management or other departments with the requirement we need to meet, an idea to implement that either makes their jobs easier or streamlined somehow, and examples of how being in compliance ahead of time is going to save them in the long run.
Slowly, but surely, I get people to come around and believe in the new system. Companies I've worked with started out as "Oh, that SQF stuff? Put it in a binder and we'll open it next year when the auditor comes." But teaching them that we need to have the full year's worth of records in place, we need to conduct these trainings to survive the audit, etc., eventually brought them around (especially when they took hits on that next audit for not participating).