I can't tell whether you're looking to train others yourself or looking for training, so I'll answer both ways.
"Agile" is simply a word that the manifesto authors chose. Anyone can call themselves "Agile", and anyone can be an Agile Coach. However, coaching requires a different set of skills to merely being an Agile expert - think Life Coaching skills, NLP (the bits that work), also Systems Thinking, and probably more that I'm still missing. There are certificates you can get in various coaching skills. I survive as an independent coach without any formal certification, so it's not essential.
If you're looking to become an Agile coach yourself, the best way to get involved is to meet other coaches. You could try Agile conferences, local events, etc. - there's more work out there than we can handle, so we tend to be more supportive than competitive. You'll also find us willing to pass on good books, training tips, etc., and help you find good coaches in your area. The Agile Alliance doesn't offer any formal training itself (AFAIK), but is a "community home" where you can find trainers and events.
I've seen companies require CSM certification. This is only a 2-day course, so if you've got reasonable experience in a genuinely Agile team you may be able to persuade the company to take you on anyway. I prefer teams with experienced Agilists to those who've just been on a course - it's never quite as simple in real life! CSMs are qualified to act as Scrum Masters. This is not the same as coaching or training a team.
If you're looking for a reasonable training provider, try asking them how they apply Agile principles in their own work and practice. Lots of training providers are capable of talking the talk. Fewer actually adhere to the principles they espouse.
Regarding Scrum certification - in theory, anyone can teach this. However, there's quite a lot of difference between Scrum and other Agile methodologies, so if someone hasn't been formally trained, they probably aren't teaching pure Scrum. This may not be entirely a bad thing, as Scrum relies on a particular context that can be hard to achieve (everyone co-located, cross-functional team, engaged product owner who understands all stakeholders' needs, etc.)
However, the Scrum Alliance have been known to throw their weight on occasion, so I'd look for legal advice before trying to set anything up in this space. Other Agile / Lean coaches may offer a mix of different methodologies, including XP, Kanban, DSDM, Crystal Clear, etc.
Scrum.org and the Scrum Alliance both offer Scrum training. The Scrum Alliance has the CSM / CSP / CST certifications that you're probably most familiar with. Scrum.org has splintered off recently from the Scrum Alliance, so much of the material is likely to be the same, but named "Professional" instead of "Certified".
Many in the Agile community are wary of certification. It's no substitute for experience. The PMI certification requires experience rather than just attendance on a course, so it's likely to be more valued and valuable.
