Even though you are ultimately responsible for your graduate education, having a good advisor certainly doesn't hurt! The qualities of a good advisor depend just as much on the student as on the professor - one student might flourish with a professor, while another might founder. So, choose carefully, and think about what you want to get out of the advisor-student relationship (and what your major professor will expect!).
Many folks will choose an advisor based on his or her reputation - and this is certainly something to consider. A "famous" advisor may be able to open doors that wouldn't be available otherwise, in terms of contacts and opportunities. But, be careful - a famous scientist is not necessarily a good advisor. Be especially thoughtful about the other factors outlined below. . .
What sort of advisor do you want? Hands-on? Hands-off? Both kinds of advisors are out there, and both can be excellent - if your personality is matched to theirs. If you are a little less sure what you want to do, and if you feel like you'll need a little more guidance through your graduate career, a more hands-on advising style is probably appropriate. The "hands-on" style covers a whole range of styles - from weekly meetings and heavy guidance in choosing a project, to occasional reminders to provide manuscript drafts and dissertation outlines. A hands-off advisor won't beat down your door for constant progress reports, or nag you about dissertation progress. This is nice in that it might let you do your own thing - but it can be a double-edged sword if you need a little motivation now and then. And, will the hands-off advisor be there if you need him or her to read papers, write letters of recommendation, or offer career advice? Here, it's best to talk to other students of the advisor.
Many students (myself included) gave the research interests of their advisor some heavy consideration. It's certainly important - after all, you want to find someone who can give you the best guidance and feedback on your graduate research. But, this isn't necessarily hyper-critical. Many excellent paleontologists have trained under advisors who worked on completely different taxonomic groups or research techniques. And, you probably want to avoid becoming a clone of your advisor - this might make for a very smooth grad school experience (or not!), but it is critical to start developing skills as an independent researcher as soon as possible.
Perhaps the most important piece of advice I can offer - don't just choose an advisor. Choose a department. By this, I mean look for a place where there are several people who might be potential advisors (even in the most informal sense). In a worst-case situation, it means that you have a back-up plan if your advisor leaves for another position or if you have personality conflicts (this does happen!). In the best case, it means you have that many more people with whom you can interact. Some of the best feedback I've gotten on my dissertation has been from the physical anthropologists in my department - and they've never touched a dinosaur in their lives! Yet, the fundamental questions are the same - and good science is always good science, no matter what the topic.
Up next: Geology or biology?