Its a big question for a Forum. Start off by outlining what you are trying to achieve - is this a full comprehensive assessment of capabilities or a more simple verification of compliance with the QA system or applicable codes, standards or regulatory requirements.
First question is do they have a formal QA system and from this and by leveraging many of the QA guidance documents you can develop an audit checklist of items that directly impact quality of the performance and then rank them in order of criticality.
Remember an effective NDE system is made up of many components the trick is to decide which ones are critical to the delivery of NDE for your application and focus in on them.
I suggest you look at ASTM E 1359 - Standard Guide for Evaluating Capabilities of Nondestructive Testing Agencies and E 543 - Standard Specification for Agencies Performing Nondestructive Testing. Both of these will help you decide what to audit. Alternatively, you could hire a company who has experience in auditing NDT service providers.