It depends on which Technology  you are looking for a job. Also most of the time the marketing side of the consultancy plays a major role in determining how long you will have to wait. You should be able to get a job within 2 months(if you are taking any training and if you are smart enough), if not within 3-5 months at max. There are so many consultancy which can get you into an interview right after you are done with their so called 'training' stuff. Rest depends on you. If you are not getting any interview calls for a long time , you may want to check the job aspect of the technology that you have chosen and if its not good enough, you can think of going to other technology.
Good luck