Even though it seemed like a long time, what with the rejections and submitting three separate books and the fact that when you're my age everything seems longer, I got an agent last month after I started querying in summer 06...so somewhere around a year and three months.
And I consider getting an agent in that amount of time to be fairly lucky. Though some people get agents quicker than that, a lot of people--some of them have posted here--have spent much more time querying before they got an agent.
If there's one thing I've learned about the publishing industry, it's that it's slow. Though it's hard and you will probably obsessively check your email, you have to at least try to be patient.
Also, you have to be persistent. My first novel did not get an agent. My second novel did not get an agent. My fourth novel written (third novel submitted-the novel I wrote third is resigned to a spot in the drawer) did, however, even though I felt far along in the submission process and was worried that it wouldn't get an agent either. You know what I would've done then? Polish the next ms. and send that one out!