There are 'roving' bands of scam artists that follow storm damage, and try to take advantage of people. So the first step in finding a reputable contractor is your local directory. IF the contractors canvassing the area aren't listed, don't call them back.
Second... talk to your local Chamber of Commerce and Better Business Bureau to compare names.
Another good source is your local building supply company. Good contractors buy quality product to work with, and when they're good... they're busy. Which means repeat business, usually at the same store...thus... the store knows them on a personal basis. If you live in a small town, or rural area, the local hardware store would be a good place to check too. Most of the time, the employees who have been with these stores know who has a good reputation and who doesn't. I would even go so far as to ask the insurance company for a reference as to who normally does their work for them. This would be particularly handy, if that particular contractor's estimate is higher than the insurance paid you, in the event you have to fight the insurance company for a better settlement.
Now... with regards to what has happened so far.... you contacted your insurance company, and accepted a check from them. Unfortunately, the insurance company's goal is to pay as little as possible.... surprise.... Quite often, the initial offer from an insurance company is NOT enough to cover the true cost of replacement. If you had any kind of deductible, that came off the top, and they also calculate a certain amount of 'depreciation' into their estimate. For example... if the existing roof was rated to last 20 years, and it was 10 years old, then the insurance would take a low replacement estimate, divide the cost by HALF, because of the age of the roof, and then subtract your deductible. So... depending on the age of the existing roof, and your policy, you may end up seeing estimates quite a bit higher than what the insurance paid you for. They loved you by the way... for letting them cut you a check before you had any quality estimates in hand.
Ok, with all of that said... hail damage usually results in damage to the shingles themselves (assuming this is a shingled roof), and occasionally the felt paper (aka 'tar paper') underneath. If you have only one layer of shingles, then you may be able to simply add a second layer on top. This would be your least expensive approach. You'll need to check the building codes in your area though. A three layer limit is pretty common across the country, but I understand some places are getting downright difficult, and want to limit homes to just a single layer of shingles. If codes do not allow you to place another layer of shingles on the roof, then you're going to have to do a 'tear-off', which is removing all the old shingles, and starting fresh. With this approach, you've got to pay for the labor of removing the old shingles and tar paper, AND disposal of them. This can double the cost of a new roof.
Always get multiple estimates. Always get references and CHECK THEM. Talk to previous customers. You might find that while a 'reference' roof looks good, the contractor was a nightmare to work with, leaving trash about, poor manners, all kinds of things that could have a negative impact. Do NOT assume the lowest, or highest, estimates are the 'best'. ASK questions. Make them compare apples to apples. If one estimate is quite a bit different from others, ask WHY (high or low...find out why their estimate is so much different). Lets face it.... the cost of supplies is going to run pretty much the same for any contractor... they all get about the same discount from where they buy their supplies. That leaves labor, overhead, and profit margins to play with. If one bid is quite a bit lower than the others, it may be because that contractor isnt carrying insurance like he should. Speaking of insurance, ask the contractors as you whittle the list down to provide the names of their insurance providers... liability, and workman's comp insurance. Any contractor that works on a steady basis WILL have these types of insurance. "Fly by night" contractors often will NOT. Liability insurance covers YOUR home in the event the contractor or one of his employees does something to damage your home (like when a plumber accidentally sets fire to the wall when sweating copper pipes, hehe), and workman's comp insurance covers his employees in the event of an accident. If a contractor does NOT have workman's comp... guess who pays the bills for a worker that falls off YOUR roof? You Do.
If you don't have any leaks yet in the roof, then you've got some time to work with here. And the prices may come down, closer towards fall, as the roofing contractors are winding up their seasonal business. Don't dawdle though.. start looking for a quality contractor now.