My recommendations for Prolog books are not the only books that I have read on the subject, (far from it!), nor are they the only books that I think have merit. They are the books that I consider to be the best.
Prolog is a deep subject, rather than a broad one, so it is best studied in stages.
Clocksin & Mellish's Programming in Prolog is the definitive introductory text on Prolog. Most importantly, it will help you to start programming straight away.
I regard Peter Flach's Simply Logical: Intelligent Reasoning by Example as the best advanced text currently available. It deals with both theoretical and practical aspects of logic programming, but doesn't assume prior knowledge beyond that you will have gained from "Programming in Prolog".
Robert Kowalski's Logic for Problem Solving, also known simply as "Bob's book", is Logic Programming's mother lode - essential reading.
It's been out of print for a while now, but used copies turn up regularly. Failing that, the book has been scanned into PDF format and can be downloaded from Robert Kowalski's homepage.
If you're going to use Prolog "for real", it is likely that it will be to solve a complex problem, so it is inevitable that performance and memory utilisation will be important.
David Harel's Algorithmics is a very accessible treatment of program "behaviour". It isn't tied to any programming language, and the techniques described are readily applicable to Prolog programs.
Richard O'Keefe's The Craft of Prolog is a superb exposition of the techniques that can be employed to work with Prolog, rather than fighting against it, and the rationale behind them.
