Nothing prohibits you from interviewing. . . but it may limit what you discuss and where you can take the job from a location perspective so re-read the agreement. You don't have to hire a lawyer until things are looking like you're going to consider the new employment as a real opportunity, so just consider this an issue that needs to be resolved before taking a job. You're wise to start thinking about it in advance.
The applicability and enforceability of non-compete clauses varies. NM seemingly follows the traditional concepts of non-competes, however, in California, where I practice, the non-compete is almost never enforceable against a former employee (as a seller of business, yes). Unfortunately, you're not that lucky, unless you're moving to California. The politics behind the enforcement of non-competes also changes from time to time, so a lawyers paid advice is something that you need before you act. Otherwise, you could be dismissed from a new job as a result of failing to disclose the obligation to the new employer (Companies don't want legal disputes, unless you're the Steve Jobs of your field.).
For now, focus on the terms defining the scope of the prohibited activity and whether this would describe your job functions and tasks in your new job (interpreted reasonably and fairly), and whether the location which you'd work from is defined by the agreement. Depending upon the this defined scope, the geography and the duration, the non-compete could be considered unreasonable and unenforceable, but these need be read together. If it's long-lasting, broad in scope and covers a vast geography, the employer could have a problem enforcing it, but that doesn't mean that they can't make you and your new employer miserable in the process. On the other hand, if its short term, very narrow in scope and covers only the general area where you currently work, you could be prohibited from taking the new job.
You would also want to discuss the non-compete with the prospective new employer if things were moving in that direction, but this isn't something that you may want to raise in the first interview, second interview, yes. A discussion that you'd have where you tell them that you're subject to such provision and that you're planning on hiring an attorney to assist you. The company may also want you to clarify the obligations so they can measure their own risks.
Non-compete agreements can be a tricky situation in that I've seen companies assert these provisions in instances where they don't precisely apply because employees leave under less-than-desired conditions, so keeping things above board with the company departed before and after you leave is always prudent.
PS - You should not consider this as counsel or legal advice. Consult a NM attorney with the specifics of your circumstances so that an appropriate determination can be made. I'm enjoying the exercise.