"Go for Beginners" by Iwamoto is a classic [1].

"Go: A Complete Introduction to the Game" by Chikun Cho generally gets very high recommendations [2].

When you finish your first book a good followup is "The Second Book of Go" by Bozulich [3].

Finally, the series "Graded Go Problems for Beginners" is excellent [4]. Volume I problems are suitable for beginners starting as soon as you learn the rules.

If you have an iOS device, take a look at smartgo books [5]. Chikun Cho's book listed above and the graded go problem series are available from them, as are many many other books. These books are in an interactive format that works with their free reader app.

[1] http://www.amazon.com/Go-Beginners-Kaoru-Iwamoto/dp/03947333...

[2] http://www.amazon.com/Go-Complete-Introduction-Beginner-Elem...

[3] http://www.amazon.com/Second-Book-Beginner-Elementary-Books/...

[4] http://senseis.xmp.net/?GradedGoProblemsForBeginners

[5] http://gobooks.com

Right now I'm working through the book "How Not to Play Go", by Yuan Zhou, but he has many very good books I could recommend. Neil Moffatt is another good writer, and I particularly enjoyed "Double Digit Kyu Games" by him. If you're not afraid of diving right in, Yuan Zhou's "Master Play" series, where he dissects games by different Go masters are very entertaining as well.

You can lurk the go subreddit /r/baduk (baduk is the Korean name for go, helpful for web searches now Google killed the term) and Sensei's Library: http://senseis.xmp.net/ a wiki for and from go players.