Different states do it differently. Most master's degrees are not ABET accredited, so some states use the criteria that the master's degree must be from a school whose undergraduate engineering program in the same discipline is accredited. You may also have to apply for the "ABET equivalent" route where they count how many credits you had in each category (graduate or undergraduate) and see if what you have is substantially equivalent to an ABET engineering degree. There's also an experience-only route for some states. If you have 6 years experience, you qualify to sit for the exam in California even if you don't have any college degree.
Some state laws about this are just stupid. For example, if you have your BS in Physics and a Master's in Engineering, some states will still turn you down. There's no reason for a working professional with his/her master's degree to go backwards and take classes with a bunch of kids just to satisfy their stupid requirements. I don't think the boards really expects anyone to do that, they just want to deny enough people to keep the credential exclusive, without regard to who they're accepting or denying.
That said, the laws vary from state to state enough that I think most people getting screwed by their own state can probably find another state that will let them take the test. The legal power of the PE has nothing to do with where you live or work, it applies to projects located in that state, so having an out of state PE is no more invalid than having an in state PE while working on a project in another state (which is common). Also, I don't know from experience but I would think that the boards would be more willing to consider unusual circumstances with regard to comity than they would for accepting someone to take the exam.
Therefore, if possible, I recommend finding a state where you qualify without question, then applying to your home state for comity/reciprocity when you think you qualify for their requirements. That's what I'm doing. I have my BS in Math and 6 years experience, which qualifies me to sit for the exam this April in Virginia. Once I finish my Master's in Mechanical Engineering I will apply for comity/reciprocity in my home state, making the argument that my education is ABET equivalent.
