I realize this question isn't strictly mathematical, and if it doesn't fit with the content on this site then feel free (moderators/high-rep users) to close it. But when I thought up the question it seemed to me that the users on this site would be best equipped to answer it.

I've always been intrigued by the paintings of M.C. Escher comprising infinitely repeating patterns. For those of you not familiar with his work, here's an example, titled Angels & Devils:

I recently wrote a blog post about the above picture and then started thinking: how did Escher do that? It's kind of like a fractal, right? (Or is that an extremely ignorant thing to say?)

Maybe if I were to attempt such a painting myself, today, I could find a computer program to generate random fractal-like patterns over and over until I found one I felt I could work with; then I could simply "fill in the space" with whatever image I chose. But surely Escher didn't have any such tool available to him, right?.

So: how might Escher have designed such patterns? Does anyone have any mathematical insight into what process might have been used to accomplish this? Alternatively, does anyone possibly have some historical knowledge of how Escher actually did do this?