A few ideas:
Ask for references. This can work nice, but since the contractor can choose which references to give you, doesn't always give an accurate picture.
If they are in a regulated trade (electrician, plumber, builder, etc.) ask your local city code inspector. They know all the contractors and know which ones do good work and which ones do just enough to pass inspection.
Check with your local building/plumbing/electrical supply stores. They know the contractors and which ones are good or bad.