What are you educating them on? E/M? Specific procedures? Without knowing what you are attempting to convey, it's hard to give you specific pointers, but here's some general suggestions.
One thing I've learned over the past 20+ years of doing this, is that providers will give you 10 minutes of attention. Make your training short, to the point, and tackle just one or two topics at a time. Use handouts, cheatsheets, and other tools for them to use as references, based only on regulatory guidance. When training them, use their own notes as examples of what to do (and what to avoid). Be sure to point out how they're being successful. If you approach them only to tell them what they're doing 'wrong', they'll run when they see you! Ask them to teach you about what they do. Not only will this help you understand their rationale, it might change how you think about their documentation. Remember, your job is to make sure they get paid for what they do, not to tell them how to practice medicine. You provide a service, not a police action! Make sure you are knowledgable, and if you aren't sure, say so, and promise to get back to them. Be confident, be able to pronounce your terminoloy correctly, have backup to prove your points, and be prepared. The worst thing you can do is waste their time.
One example of the tools we use are 3x5" laminated cheat sheets of the E&M Key components (you can make these up in Excel), and each office (we have 14) has a coding manual for their reference. Other handouts and references can be specialty specific. We follow up each training session with at recap in an email, and we always make sure our training sessions are at their convenience. We sometimes do lunch 'n' learn sessions, or we meet prior to their morning rounds or appointments.
Hope this helps.