Seconding The Reasoned Schemer for learning miniKanren. It's a complete tutorial compared to most you'll find online that either quickly go from "here's how to start" to "now here's us generating lisp functions from specifications" or never move past the "here's how to start" portion.
And like all the Schemer books, it's a pretty pleasant and easy read. You can go through a chapter sans computer and then revisit it with the computer (I read it while traveling so half the time I was reading, my computer wasn't readily available).
I'd suggest just poking around in these first:
http://io.livecode.ch/ online interactive minikanren examples
http://tca.github.io/veneer/examples/editor.html more minikanren examples.
You already mentioned http://minikanren.org/ You may also want to check out the book The Reasoned Schemer.
I did a slightly faulty implementation ( I didn't get the search ordering right) in Julia here https://www.philipzucker.com/yet-another-microkanren-in-juli...
Microkanren implementation tutorial https://www.youtube.com/watch?v=0FwIwewHC3o . Also checkout the Kanren online meetup recordings https://www.youtube.com/user/WilliamEByrd/playlists