What are the conditions for a polygon to be tessellated? Upon one of my mathematical journey's (clicking through wikipedia), I encountered one of the most beautiful geometrical concept that I have ever encountered in my 16 and a half years on this oblate spheroid that we call a planet.
I'm most interested in the tessellation of regular polygons and their 3D counterparts.
I've noticed that simple shapes like squares or cubes can be tessellated but not circles or spheres.

Somewhere after hexagons, shapes lose that ability to be tessellated by only themselves. Although it is intuitively clear to me when  shape can be tessellated, I cant put it into words. Please describe to me, in a fair amount of detail, what the lesser sided shapes had that the greater sided shapes did not inorder to be tessellated.
 A: A regular polygon can only tessellate the plane when its interior angle (in degrees) divides $360$ (this is because an integral number of them must meet at a vertex). This condition is met for equilateral triangles, squares, and regular hexagons. 
You can create irregular polygons that tessellate the plane easily, by cutting out and adding symmetrically. 
A: First, let's see the case that we use only one polygon and its copies to tessellate the plane.
(1) We can easily prove that there are only three regular polygons $(n=3,4,6)$ which tessellate the plane with one polygon.
(2) You'll see that any parallelogram can tessellate the plane. (I found some figures here though the language is Japanese.)
(3) The fact (2) means that any triangle can tessellate the plane because you can make a parallelogram using two copies of a triangle.
(4) A hexagon with three pairs of parallel edges can tessellate the plane. 
(5) The fact (4) means that any quadrilateral can tessellate the plane because you can make a hexagon with three pairs of parallel edges using two copies of a quadrilatelral which is not a parallelogram. 
(6) Some pentagons with a special condition can tessellate the plane. For example, you can divide a hexagon of (4) into two congruent pentagons. 
Second, let's see the case we can use more than two distinct polygons and its copies to tessellate the plane. 
You can find helpful comments in other's answer. Also, you'll find some figures in the same page as above. For example, (3,3,3,3,6) means there exist four equilateral triangles and one hexagon at every vertex. 
I hope you like this answer.
Edit 1 : This is a question which I asked at mathoverflow. You may be interested in the question. 
Edit 2 : Let us consider $3D$ version. Fedorov found that there are exactly five 3-dimensional parallelohedra. You can see beautiful figures here. You'll be interested in these figures.
A: It's all about angle sums. You can only fit 2$\pi$ worth of angles around each point, and large polygons have so large that you can't fit an even amount around ach vertex.
In sherical geometry, you have add up to less than 2$\pi$, and this gives you the platonic solids.
In hyperbolic geometry you can tesselate by regular polygons with any number of edges.
A: The question you are asking is by no means trivial. But you can gain some intuiton using the Euler Characteristic. 
A graph can be viewed as a polygon with face, edges, and vertices, which can be unfolded to form a possibly infinite set of polygons which tile either the sphere, the plane or the hyperbolic plane. The Euler Characteristic is $\chi = V - E + F$, where V is the number of corners (vertices), E is the number of edges and F is the number of faces.  If the Euler characteristic is positive then the graph has an elliptic (spherical) structure; if it is zero then it has a parabolic structure, i.e. a wallpaper group; and if it is negative it will have a hyperbolic structure. When the full set of possible graphs is enumerated it is found that only 17 have Euler characteristic 0. 
You can test the function (Euler Characteristic) with any polyhedron, for example. You will find that $\chi = 2$. So, in some sense, it is a measure of the curvature of the space you are in. Proofs involving the Euler Characteristic can be extremely simple, but may be really complex too (it is widely used in algebraic topology). In any case, however, the function gives conditions on the polygons you are working with. I remember a very simple of proof of the fact that any polyhedron has at least a face that has 5 sides or less:
Proof: At any vertex, you have 3 or more edges, so $V \leq \frac{2A}{3}$. Suppose that all faces have 6 sides or more: then, $F \leq \frac{2E}{3}$. Now, the Euler's formula gives  $E + 2 = F + V \leq \frac{2A}{3} + \frac{2E}{3} = A$, which is a contradiction. This completes the proof. 
So any tessellation has a fundamental restriction in Euler's formula (in our case, it is 0 = V - E + F).
As for the tessellations in itself, it's not exactly the shape of the polygon that matters, but its simmetry group.
Imagine you want to invent a pattern to make a tessellation. A symmetry of a pattern is, loosely speaking, a way of transforming the pattern so that the pattern looks exactly the same after the transformation. For example, translational symmetry is present when the pattern can be translated (shifted) some finite distance and appear unchanged. Think of shifting a set of vertical stripes horizontally by one stripe. The pattern is unchanged.
Sometimes two categorizations are meaningful, one based on shapes alone and one also including colors. When colors are ignored there may be more symmetry. 
The types of transformations that are relevant here are called Euclidean plane isometries (translations, rotations, reflections and glide reflections). So, in detecting a pattern of a tessellation, sometimes it is easier to detect the isometries than the pattern itself. And is using these isometries that patterns can be created. 
There are exactly 17 distinct groups, which means that there are 17 different ways to make a tessellation (all of which, by the way, can be found at the Alhambra). It is the two dimensional case of a more general problem: the 3D case, for example, can be interpreted as the number of different crystaline structures. 
If you want to see how to create all 17 different patterns, look at here. There are som animated gifs that I made some time ago. 
For more information on the wallpaper groups, read this.
