The answer by Nick S is essentially correct, but I can provide a little more detail.

It is not hard to show that the tiling problem (if a set of shapes admits a tiling of the plane) is decidable if every set of shapes that tile admit a periodic tiling. The algorithm is to put shapes together, look at the way two shapes can combine, 3 shapes and so on. If the shapes cannot tile you will eventually find a ball that cannot be covered, if they can tile periodically you will eventually find the patch that can go periodic.

The discovery of aperiodic tilings and the result that the tiling problem was undecidable were proved at the same time by Berger. In fact Berger used an aperiodic tiling to show that the tiling problem was undecidable (originally in his thesis). Note that he (and others) call it the "domino problem", as the question was originally posed for squares with coloured edges, called Wang tiles.

R Berger The undecidability of the domino problem

*Mem. Amer. Math. Soc.* **66** 1966

http://books.google.com/books/about/Undecidability_of_the_Domino_Problem.html?id=8AmiHD0Lbu8C

Berger's proof was significantly simplified by Rafeal Robinson. An important part of the simplification was considering a smaller set of aperiodic tiles. Berger's example required 20,426 tiles, whereas Robinson's required just 6.

R M Robinson, Undecidability and Nonperiodicity for Tilings of the Plane

*Inventiones math.* **12** 177-209, 1971

http://www.lif.univ-mrs.fr/~fernique/qc/robinson.pdf

Although it proved useful in these proofs, the existence of aperiodic tilings is not equivalent to the undecidability of the tiling problem. For one thing, by definition, the tiling problem is decidable for all known aperiodic tilings. The best case for the tiling problem is a result of Nicolas Ollinger. He shows that the tiling problem is undecidable for sets of 5 tiles using a construction based on polyominoes.

N Ollinger, Tiling the Plane with a Fixed Number of Polyominoes.

Proceedings of LATA 2009, *Lecture Notes in Computer Science* **5457**, Springer 2009, pp. 638-647.

http://www.springerlink.com/content/x5nkq3640w6784w4/

For the question of aperiodic sets of shapes, we have had examples with two tiles (e.g. the Penrose tiling) for a long time, although there are still only a handful of examples with a small number of shapes (<10 for example). The question of a single tile was a longstanding open question, and became known as the einstein problem (a german pun). The answer now depends on your definition of "tile". For a permissive definition (a tile is a compact set that is the closure of its interior, for example) the problem was solved by Joan Taylor, who is not a professional mathematician but decided to take on this particular problem over several years. This is a significant development, but perhaps not the final answer. The tile that she found is not connected. With respect to the setting of this question, the boundary is not a closed Jordan curve, and, for me, this means that it fails "the laser cutter test" I cannot easily make the thing! This result is the preprint given in Richard Borcherds comment:

J E S Socolar, J M Taylor An aperiodic hexagonal tile

*Journal of Combinatorial Theory, Series A* **118** pp. 2207-2231 2011

http://arxiv.org/abs/1003.4279

I wrote a little bit about the story here:

http://maxwelldemon.com/2010/04/01/socolar_taylor_aperiodic_tile/

and you can also find Joan Taylor's original paper, with beautiful hand-drawn images:

http://www.math.uni-bielefeld.de/sfb701/files/preprints/sfb10015.pdf

On the hyperbolic plane the first strongly aperiodic set (having no symmetries of infinite order) was discovered in 2005, by Chaim Goodman-Strauss:

C Goodman-Strauss A strongly aperiodic set of tiles in the hyperbolic plane

*Inventiones Mathematicae*, **159**, Number 1, 119-132, 2005

http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf

The tiling problem took a little longer, and was only shown to be undecidable recently (in 2006-7), independently by Maurice Margenstern and Jarkko Kari, who give distinct proofs.

M Margenstern, The Domino Problem of the Hyperbolic Plane is Undecidable

*The Bulletin of the EATCS* **93** 220--237 2007

http://arxiv.org/abs/0706.4161

J Kari, On the Undecidability of the Tiling Problem

SOFSEM 2008: Theory and Practice of Computer Science
*Springer Lecture Notes in Computer Science*, **4910**, 74-82 2008

http://www.springerlink.com/content/673165n258t18741/