How might M.C. Escher have designed his patterns?

'Around 1956, Escher explored the concept of representing infinity on a two-dimensional plane. Discussions with Canadian mathematician H.S.M. Coxeter inspired Escher's interest in hyperbolic tessellations, which are regular tilings of the hyperbolic plane. Escher's works Circle Limit I–IV demonstrate this concept. In 1995, Coxeter verified that Escher had achieved mathematical perfection in his etchings in a published paper. Coxeter wrote, "Escher got it absolutely right to the millimeter."'

http://en.wikipedia.org/wiki/M._C._Escher

If Angels and Devils is a hyperbolic tessellation then it might have been inspired by Coxeter.

The construction itself was done using techniques like these:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.8746&rep=rep1&type=pdf

The June/July 2010 issue of the AMS Notices here has a further article by Doris Schattschneider (a graduate school classmate of mine) on Coxeter and Escher. Doris has written extensively about Escher's work from a mathematical viewpoint, so it's worth checking out her point of view.

P.S. Don't overlook in this Notices issue Bill Casselman's column About the Cover.

I think he knew about hyperbolic geometry you can read more here:http://www.math.cornell.edu/~mec/Winter2009/Mihai/index.html

There is also a beautiful article in the notices of the AMS by H. Lenstra and B. de Smit, (http://www.ams.org/notices/200304/fea-escher.pdf), in which they explain how he painted the "Print gallery" (it involves complex geometry). They also show how to fill the hole in the center of the painting, you can actually see it at dedicate web site (run by Bart de Smit) http://escherdroste.math.leidenuniv.nl/