Talk to your purchasing and the accounting folks etc. if you have some, they should have some idea. Now from an Engineering point of view the relative priorities you put on things may be a bit different but still, worth getting their input in what - in theory at least - is their area of specialization.
What are their inspection capabilities & can they understand the symbology on your drawings such as GD&T etc.
Ease of communication.
Do they have compatible software etc. if required - or do you have a work around if necessary.
Recommendations/References from their customers are almost worthless - they'll only ask people they've impressed to provide reference. The guy they screwed over will not be volunteered as a reference. However, it can provide a nice warm feeling, and if you carefully ask questions you may get useful info.
Similarly, just because they can show your their certs that they are ISO 9001 accredited, or 'an approved Boeing supplier' or similar doesn't guarantee they'll be a good vendor. However, that doesn't mean it has no worth.
Try and get some assessment of their customer service, do they supply first article inspection reports, what are their typical lead times, how do they package parts...
Then there's the risk management element, especially if they are going to be a 'major' or 'strategic' supplier.
There's financial risk - are they going to go bankrupt with a bunch of your parts that you need urgently in process. Even worse if they hold some kind of tooling or raw stock etc. that you paid for. While I don't know what is reasonable to ask for, and depending on location what's legal etc. this is where your purchasing/accounting folks may be able to help.
There's also physical risk, you don't want the place burning down, or similar with your parts or tooling on their shelves. One place I looked at as a vendor made 90% of the 'widgets' that go in Guinness and similar beers. Due to this Guinness did a big risk review looking at things like their location relative to local airfields in case of plane crashes, as well as more mundane things like flood risk, earthquake, fire prevention practices etc.
The physical risk aspect probably isn't widely assessed in most cases but maybe it should be.
Posting guidelines faq731-376 (probably not aimed specifically at you)
What is Engineering anyway: faq1088-1484