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.)

[0] http://en.wikipedia.org/wiki/Warren_Abstract_Machine [1] http://wambook.sourceforge.net/