I am quite fond of Peter Shotwell's book "Go Basics" - it teaches all the rules, and goes through a lot of basic concepts, all through the use of professional games. The way it manages to do this is by focusing exclusively on the 9x9 game - where a 19x19 professional game would be way above the head of a beginner, in 9x9 the reasons behind the professional players' moves are much more immediate, and understandable even by a beginner with the help of the author's excellent commentary. As I would always recommend beginners to start playing on 9x9 until they have built up their experience and skill, I think his approach makes excellent sense - it is much harder to grasp why you are losing on 19x19 when you are just starting out, while 9x9 keeps the strategy manageable and allows you to focus on building up basic skills before taking on the complexity of the full game.

Otherwise, as several people have said, the Janice Kim books are excellent - the first two are enough to get off to a good start. They are well written, and explains thing clearly. They are also a comparatively light read - not too hard to digest.

The first two volumes of Graded Go Problems for Beginners would make excellent companions to either Shotwell or Kim - not much in the way of expositionary material, but instead practice of basic patterns that occur over and over in actual gameplay - going through those exercices helps ingrain tactical skills.

I would recommend against getting Charles Matthew's Teach Yourself Go as a first book - while it is a good book, and I learnt several things from reading it, it is also very dense, and requires a lot more from the student in the way of determination and focus than the books mentioned above.