Definition
A tessellation is created when a shape is repeated over and over again covering a plane without any gaps or overlaps.
Another word for a tessellation is a tiling. Read more here: What is a Tiling?
A dictionary* will tell you that the word "tessellate" means to form or arrange small squares in a checkered or mosaic pattern. The word "tessellate" is derived from the Ionic version of the Greek word "tesseres," which in English means "four." The first tilings were made from square tiles.
A regular polygon has 3 or 4 or 5 or more sides and angles, all equal. A regular tessellation means a tessellation made up of congruent regular polygons. [Remember: Regular means that the sides and angles of the polygon are all equivalent (i.e., the polygon is both equiangular and equilateral). Congruent means that the polygons that you put together are all the same size and shape.]
Only three regular polygons tessellate in the Euclidean plane: triangles, squares or hexagons. We can't show the entire plane, but imagine that these are pieces taken from planes that have been tiled. Here are examples of
When you look at these three samples you can easily notice that the squares are lined up with each other while the triangles and hexagons are not. Also, if you look at 6 triangles at a time, they form a hexagon, so the tiling of triangles and the tiling of hexagons are similar and they cannot be formed by directly lining shapes up under each other  a slide (or a glide!) is involved.
You can work out the interior measure of the angles for each of these polygons:
Shape
triangle
square
pentagon
hexagon
more than six sides


Angle measure in degrees
60
90
108
120
more than 120 degrees

Since the regular polygons in a tessellation must fill the
plane at each vertex, the interior angle must be an exact
divisor of 360 degrees. This works for the triangle, square,
and hexagon, and you can show working tessellations for these
figures. For all the others, the interior angles are not
exact divisors of 360 degrees, and therefore those figures
cannot tile the plane.
Naming Conventions
A tessellation of squares is named "4.4.4.4". Here's how: choose a vertex, and then look at one of the polygons that touches that vertex. How many sides does it have?
Since it's a square, it has four sides, and that's where the first "4" comes from. Now keep going around the vertex in either direction, finding the number of sides of the polygons until you get back to the polygon you started with. How many polygons did you count?
There are four polygons, and each has four sides.
For a tessellation of regular congruent hexagons, if you choose a vertex and count the sides of the polygons that touch it, you'll see that there are three polygons and each has six sides, so this tessellation is called "6.6.6":
A tessellation of triangles has six polygons surrounding a vertex, and each of them has three sides: "3.3.3.3.3.3".
Semiregular Tessellations
You can also use a variety of regular polygons to make semiregular tessellations. A semiregular tessellation has two properties which are:
 It is formed by regular polygons.
 The arrangement of polygons at every vertex point is identical.
Here are the eight semiregular tessellations:
Interestingly there are other combinations that seem like they should tile the plane because the arrangements of the regular polygons fill the space around a point. For example:
If you try tiling the plane with these units of tessellation you will find that they cannot be extended infinitely. Fun is to try this yourself.
 Hold down on one of the images and copy it to the clipboard.
 Open a paint program.
 Paste the image.
 Now continue to paste and position and see if you can tessellate it.
There are an infinite number of tessellations that can be made of patterns that do not have the same combination of angles at every vertex point. There are also tessellations made of polygons that do not share common edges and vertices. You can learn more by following the links listed in Other Tessellation Links and Related Sites.
Michael South has contributed some thoughts to the discussion.
*Steven Schwartzman's The Words of Mathematics (1996, The Mathematical Association of America) says:
tessellate (verb), tessellation (noun): from Latin tessera "a square tablet" or "a die used for gambling." Latin tessera may have been borrowed from Greek tessares, meaning "four," since a square tile has four sides. The diminutive of tessera was tessella, a small, square piece of stone or a cubical tile used in mosaics. Since a mosaic extends over a given area without leaving any region uncovered, the geometric meaning of the word tessellate is "to cover the plane with a pattern in such a way as to leave no region uncovered." By extension, space or hyperspace may also be tessellated.