They should have a certificate from Krav Maga World Wide Headquarters in LA. It will show their certification and their level they are supposed to teach. There are three different levels. (Level 1, Level 2, and Level 3). Most Instructors teach beyond what they are supposed to teach, which I feel is fine if they are teaching proper technique and/or self defense. But just remember that they are only certified by LA to teach what they have been certified on. As for checking to see if they are certified, look for their certificate on the wall or ask to see it. I imagine you can contact LA and ask them to check their records also.
If your in a "Fair Fight", your tactics suck.