you should look for the following from your consultant:
1) knowledge base - how well does he know data communications technologies? can he provide answers to you immediately or does he have to continually look them up? how many areas of the industry does he know? can he understand your business needs and convert those into 'real business' solutions? does he know routing, switching, security and web design/administration? does he follow best practices and industry standards? what certifications does he have to show his indepth study of the technologies?
2) customer service - how is the consultant when interacting with you or your partners? can he explain in 'user/nonTechie' terms what he is trying to communicate to you? does he keep focus during your discussion of what you need or would like? does he respond in a timely fashion in person, via email, by phone?
3) cost/quality - how much does this person charge? is it hourly, block of time, monthly, etc?
how does the cost compare with the amount or quality of service? do the tasks you pay for get done on time? is there overtime charges? does he provide 'service level agreements' for his work/support of your environment?
4) availability - how do you get in touch with him in an emergency? will he be onsite for all work? can he work for you remotely? how many communication paths do you have to contact the consultant; pager/cell/email...?
5) vendors - what vendors does he work with? does he have 'good business relationships' with any vendors? is he a 'certified partner' of any vendors? does he provide new, warranted, quality hardware/software from leading manufacturers or does he get these off-the-street?
6) business - how long has he been consulting? is he registered with the Better Business Bureau? does he have good, valid references? is there a company website with contact info, products and services you can use?
these are all good questions that should be answered, in my opinion, before you hand the keys to your technology needs over to anybody.
You can always give the consultant a small project and see how he does before giving him the "whole enchilada". Also I would have to disagree with the Better Business Bureau as a possible criteria for hiring, I have found the BBB to be surprisingly unethical. YMMV.
Word of mouth! Ask your friends who they use or if they know anyone. I have more side job work than I can handle and it's all from my customers telling their friends/relatives/business partners/etc.
I tend to agree with the input everyone has given. The BBB is good to be affiliated with. I did not do this with my small business since I didn't want to spend the extra money to be affiliated with the BBB.
Word of mouth is a good source, sometimes the best source. I get all my work thru people I know or word of mouth.
Make sure you get a couple of different quotes for the same job. Use the consultants to answer your questions about things you don't know. For example, if a consultant throws you some stuff you don't know, you can ask him what that is. He might say you need it (you may or may not). Then when you talk to another consultant see if his answer is different. You'll get a better idea of the topic. Good luck.
Check the Cisco partner locator, also. It'll search for companies in your local area, certified, and if they're good a star for customer satisfaction ratings. http://tools.cisco.com/WWChannels/LOCATR/openBasicSearch.do