Depending on how large a fragment of Prolog you want to implement, it can be quite simple. SICP chapter 4.4 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html...) describes a simple interpreter written in Scheme for a Prolog-flavoured languge (without cut, and also no parser).
Strictly speaking, SICP's amb implements nondeterminism (via backtracking), not Prolog. Prolog also needs unification (a more powerful form of pattern-matching), at the very least. (EDIT: Forgot about the next section, with Logic Programming.)
Many Lisp books implement Prolog. Try PAIP and/or On Lisp. PAIP puts more time into implementing it well, but On Lisp covers the main ideas. I recommend both, regardless.
Amb is in SICP section 4.3 ("Nondeterministic computing"), section 4.4. is called "Logic Programming" and is implemented using streams rather than amb. I agree that On Lisp, which does it via amb, is also nice!
For an even more dramatically simplified version, I wrote a extremely toy interpreter in about a hundred lines of SML: http://everything2.com/title/continuation+passing+style
Or of course, you can implement it in a single line of Prolog. :)