What are your experiences with them?

2$\begingroup$ I added the Big List tag, and also, this question should be community wiki, because there will be lots of answers rather than a single correct one. $\endgroup$ – Charles Siegel Jan 18 '10 at 0:42

$\begingroup$ What kind of a beginner are we talking about here? What is your experience with proofbased mathematics? $\endgroup$ – Qiaochu Yuan Jan 18 '10 at 0:45

1$\begingroup$ At least the first few chapters of Diestel are more or less elementary, if you're worried about prerequisites. $\endgroup$ – Qiaochu Yuan Jan 18 '10 at 1:16

2$\begingroup$ If someone who hasn't studied graph theory asks about it, what's the probability that they mean graph algorithms (DFS, BFS, maxflow mincut theorem...) instead of graph theory? $\endgroup$ – Douglas Zare Jan 18 '10 at 12:11

1$\begingroup$ Diestel is not really easy to understand, however... $\endgroup$ – darij grinberg Jan 18 '10 at 13:23
For an undergrad who knows what a proof is, Bollobas's "Modern Graph Theory" is not too thick, not too expensive and contains a lot of interesting stuff. Beyond this there are books by West and Diestel. I really like van Lint and Wilson's book, but if you are aiming at graph theory, I do not think it's the best place to start.

1$\begingroup$ I like that book very much, but it treats the basic material so quickly (and with so much relegated to the exercises) that I'm not totally convinced it's the best option for a beginner. $\endgroup$ – Harrison Brown Jan 18 '10 at 15:05

$\begingroup$ I remember finding astonishing numbers of typos in Bollobas, in the exercises especially. $\endgroup$ – Tom Smith May 27 '10 at 13:19

$\begingroup$ Bollobas is one of my favorite authors,but I think his books would be too difficult for any but a gifted beginner.It's better used for a second course or a supplement to an undergraduate text. $\endgroup$ – The Mathemagician May 27 '10 at 19:52
My favorite is Dots and Lines (now called Intro to Graph Theory) by Richard Trudeau. It's a supereasy and quick read with lots of fun problems that get students to experiment with examples. I usually use it in conjunction with other texts when teaching graph theory courses because students whip through Trudeau's material so fast. I've used Wilson's 4th. Ed. and that's fine; I think Chartrand/Zhang is better, but haven't actually used it in a course yet. I should say that my evaluation of a text is based on having students actually read it, as I don't lecture.

$\begingroup$ Trudeau is actually the text Dr.Kennedy used in our courseI was rather remiss in omitting it in my post,sorry,people. It's cheap and pretty good for the basics,but very old fashioned and that hinders it in some places. $\endgroup$ – The Mathemagician May 27 '10 at 19:51
Wilson (many editions)  great to read quickly to get an overview.
Bondy and Murty (2008)  very clear, lots of stuff. My favorite book.
Diestel (2005)  clinical treatment.
Bollobas (1998?)  lots of stuff, but leaves a lot of gaps for the reader to fill.
West  quite good, not read much of it.
The thing about graph theory (and combinatorics more generally, although it's especially true for graph theory) is that the basic definitions are very simple, and there is a lot of interesting math you can do without using anything but the basics.
As such, there's really only a limited benefit to just reading a text  if you want to learn the subject, you have to have to have to do problems. Of the textbooks mentioned, I personally own Diestel (free online edition) and Bollobas; of these two, Bollobas has more and better exercises (although Diestel's a wonderful reference, and has the advantage of including hints.)
Honestly, I think the really important thing when teaching/learning graph theory is for the lecturer to know what he or she is doing. Obviously some books are better than others, but none of them are very good if they're not being used correctly.
I have Gross and Yellen for the course that I'm taking this semester. Haven't looked through it, but one of the authors is my teacher and I've taken a past course with him, so I'll assume it's solid.
His other book, an introduction to combinatorics, is quite good with its definitions and explication, but the exercises leave a little to be desired.
I learned graph theory from John Kennedy and Christopher Hanusa, the former an extremely well respected graph theorist and the latter a rising young combinatorialist. There's a lot of good graph theory texts now and I consulted practically all of them when learning it. The first edition of Adrian Bondy and U.S.R Murtry's Graph Theory is still one of the best introductory courses in graph theory available and it's still online for free, as far as I know. The second edition is more comprehensive and uptodate, but it's more of a problem course and therefore more difficult. Jonathan Gross and Jay Yellen's Graph Theory With Applications is the best textbook there is on graph theory PERIOD. Rigorous and as comprehensive as it gets. The section on topological graph theory is particularly good. (I HATE their combinatorics text–it's a hodgepodge text that's nowhere near as well written and organized.) There are several other good books. Chartrand et. al isn't as comprehensive as Gross and Yellen, but quite good and in the same spirit. Douglas West's book is considered by many to be the preeminent graph theory text. I own it–it's pretty good, but not as careful and comprehensive as Gross and Yellen. If you can get a cheap copy, by all means, get West–but if you're gonna end up spending THAT much money, might as well go a little more and get the Ferrari. There's my 2 cents for what it's worth.
There are many books on specialized issues related to graphs: planar graphs, graphs on surfaces, graph coloring problems, distance in graphs, etc. However, if one is looking for a readable introduction that covers a lot of different aspects of "basic" graph theory (degree sequences, trees, colorings, matchings, connectivity, etc.), I think the best place to start is:
Introduction to Graph Theory, (Second Edition), Douglas West, PrenticeHall, 2001.
I used Graph Theory: Modeling, Applications, and Algorithms by Geir Agnarsson and Raymond Greenlaw as the basis of (part of) a masters course. I was happy with the book, although I didn't go all the way through it. It starts slowly yet covers a decent range of topics at a relatively slow pace.
I also used Graph Theory: An Advanced Course by Adrian Bondy and U.S.R. Murty (already mentioned) as a source of challenge exercises. It's a great resource.
I learned to love graphs and their counting, first from Harary's Graph Theory and later from Harary and Palmer's Graphical Enumeration, or maybe it was more the spirit of their teaching than the letter of their textbooks. These books are classics in my estimation and well worth revisiting, even if you need the supplement, as you always will, of subsequent additions to the field.
I've bought West and it seems a lot for a beginner. specially i've found the excerscises out of my reach. I don't know why it's been called one of the best books.