Most clients I know find a software contracting company thru words of mouth. Afterwards the client would visit the contractor's website, talk to someone from sales and sign the contract. Some may go a bit further and call a happy client or two (this is super rare however). For me the best way to evaluate a software contracting company is to interview the engineer as if you were hiring him for a full time position (i.e you will be working with this person for a long time). This automatically escalates things to a new serious level! The interview may last multiple hours with multiple interviewers. We at Black Gibbon even welcomes whiteboarding or live coding interview sessions (where the client's internal software engineer would interview his counterpart from the contracting firm). A nontechnical interviewing session can be included as well as it is complimentary to the tech interview sessions. Here both parties talk about the prospective project, daily workflow, task division and get to know each other informally, etc.
Besides the interviewing sessions, we find a pilot contract is a great way to vet. At Black Gibbon, we have a 100 day pilot program that lets both parties evaluate each other. At the end of the pilot, it should be obvious whether:
If unfortunately, none of the above was achieved during the pilot period then no harm done. The parties just part way.