Thanks Karthik for appreciating my Escher talk given so long ago. As you must have realised in creating this red heart pattern (or, in the spirit of Escher, is it a white dart pattern?), that creating such patterns is much more challenging than just analysing their space group. Still I enjoy the latter; so, I spent a happy half-hour determining the space group, the result of which is shown above. I already see a solution, P3m1 at your post. However, I suspect that the answer is probably P31m p31m; and, the teacher in me encourages me to explain how it is arrived at.
The central parallelogram is the unit cell, showing the symmetry elements. The continuous lines are mirror lines which are easy to identify. The mirror line of each heart in the pattern is also the mirror of the whole pattern. A set of three-fold axes are at the intersections of these mirror planes (points where the sharp corners of three hearts meet — shown in the figure with triangles, as is customary). Another set of three-fold axes without mirror planes can also be easily identified (shown in the figure). The tricky symmetry elements are the glide planes (shown in broken lines) which, honestly, I also didn’t see till I consulted the space group tables (I used the one in Kelly, Groves and Kidd).
There are three space plane groups with three fold axes, namely, P3, P3m1, and P31m (No. 14, 15, and 16) p3, p3m1 and p31m (No. 13, 14, 15) . P3 p3 has no mirrors. In P3m1 p3m1, mirror planes pass through all the three-fold axes. However, in P31m p31m, there are two kinds of three-fold axes — with and without mirrors. Since the heart pattern has both of these kinds, I believe the space plane group is P31m p31m. In fact, that this is P31m p31m is what made me realise that there should also be glide planes in the pattern, which, as I noted above, I figured out after consulting the tables.
Update on 25.02.2009: Corrections shown by strikethroughs are inspired by the comments of Cid (see below) on the original version.
 A Kelly, G W Groves and P Kidd, Crystallography and crystal defects, John WIley, 2000; pp. 85-87. A very good reference for basic crystallography.
PS: By the way, I would like to thank Guru who was persuading me for a long time now to join or to contribute to Materialia Indica (lively discussions with whom is always a joy!).