Prolog programming books
Out of the many Prolog programming books that I have read, I consider these 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.
More Advanced Applications
I regard Peter Flach's Simply Logical: Intelligent Reasoning by Example as the best advanced text. 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".
The Last Word
The original book has been scanned into PDF format and can be downloaded from Robert Kowalski's homepage.
Performance and memory utilization become important when Prolog is used to solve complex problems.
David Harel's Algorithmics is a very accessible treatment of program behaviour. It isn't tied to one 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.