I think Prim is right. Ultimately the answer of whether evolution of intelligence is common or rare can never be definitively answered without having a greater sample size (and so if we never develop the capacity of near-lightspeed travel we'll never know the answer). However, my gut tells me that, given certain conditions, the evolution of intelligent life is highly likely (inevitable was probably too strong). The fact that it's taken 5 billion years since the formation of the earth for humans to evolve is simply because it's been such a long process. First the eons it took for chemical reactions in a primordial soup to become the first truly living things, then the long, slow process of evolution. When you consider that life has moved from the simplicity of early bacteria to the complexity we find in our own brains, it doesn't surprise me it's taken so long.
And when you look at the overall trend, it seems that the net result of evolution is increasing complexity. Sure, the less complex creatures have remained, quite capable of surviving in their respective niches. But when you look at creatures like other primates, dophins, whales, horses, dogs, cats, and a host of other mammals I would consider "intelligent", you realize that self-awareness and complex thought was just the next natural step in an evolutionary process that continues to drive towards greater complexity.
True, the increased complexity of life that evolution has produced on this planet could be the exception rather than the rule. But given the time period over which evolutionary forces are acting, and the sheer diversity of organisms produced (no just currently, but historically, too), I think that intelligence is very likely to come about at some point or another on any world where evolutionary forces are at work.
The fact that intelligence did emerge so fast shows that the right conditions for that to happen must be rare. Otherwise intelligence would have gained a foothold very quickly at some point in the past when the conditions were also right.
That's the thing, Iavas. I don't think the right conditions for intelligence ever existed at any point prior to the evolution of human beings. Before this could happen, a sufficient level of neural complexity had to be attained in the brains of living things, and that was something that only the long, slow process of evolution could accomplish. However, once that precondition was set, intelligence was able to take hold quite rapidly.