Creating a simple, inefficient Prolog interpreter (that has most of the core functionality) is pretty easy (as far as implementing languages goes), especially if you're using another functional language to do it. I think it can be done in 100-200 lines of Haskell or ML pretty easily (although I haven't actually implemented one myself).
Implementing an efficient Prolog involves implementing the Warren Abstract Machine (WAM) [0]. I just implemented a very small and restricted subset of the WAM with a friend for a class final, and doing that is much harder. (Largely because there's not a whole lot in the way of documentation, and even the book that's supposed to serve as a WAM tutorial [1] is light/vague on some of the trickier implementation details.)
Another major direction for practical Prolog implementation is constraint programming. I've been studying that off-and-on for a while, and Daniel Diaz's papers on clp(FD) (http://cri-dist.univ-paris1.fr/diaz/publications/) and adding CLP to the WAM seem to be a good intro.
As silentbicycle mentions below grin, I enjoy pointing out miniKanren as a purely functional approach to building a Prolog-like system. Even at ~200 LOC the original Scheme is surprisingly efficient. My optimized Clojure version at ~1000 LOC is already closing in on SWI-Prolog on logic programs that involve a lot of unification and uninstantiated variables (such as the classic Zebra puzzle).
The high water marks for efficient Prolog implementations are Peter Van Roy's work on Aquarius and The Mercury Programming Language.
Mercury is a qualitatively different language, by the way - it adds static typing (which I'm ambivalent about, in a LP language) and AFAICT removes the ability to work with partially-instantiated data, which is one of my favorite aspects of Prolog.
Partially-instantiated data is cool/fun, but I'm starting to question its utility in programs you would actually employ for something useful. Don't hold me to that though :)
They're a good compromise between mutable and fully immutable data structures? "Oh, that? It was always there, we just didn't know about it..." Easy example: Incrementally appending to a list of conses without reversing it in the process.
Better example of working with partial information: Constraint programming.
Implementing an efficient Prolog involves implementing the Warren Abstract Machine (WAM) [0]. I just implemented a very small and restricted subset of the WAM with a friend for a class final, and doing that is much harder. (Largely because there's not a whole lot in the way of documentation, and even the book that's supposed to serve as a WAM tutorial [1] is light/vague on some of the trickier implementation details.)
[0] http://en.wikipedia.org/wiki/Warren_Abstract_Machine [1] http://wambook.sourceforge.net/