A metamaterial is a material with special properties derived from its structure rather than its chemical composition. The best known metamaterial are materials with a negative refractive index, meaning they make light bend "the wrong way" - that is, significantly more than any material with a positive refractive index.
Negative refractive index materials have applications in "superlenses" - special lenses with the potential to resolve features smaller than the wavelength of visible light, and possible invisibility cloaks that direct visible light smoothly around an object rather than absorbing or reflecting it conventionally. These materials might also be used in plasmonics, an exotic new area of computing that exploits density waves in charge carriers for computations.
Most metamaterials are used for applications relating to electromagnetism and optics, such as beam steerers, modulators, band-pass filters, lenses, etc. They are repeating grids of cellular components, with a cell size roughly equal to that of the wavelength of electromagnetic radiation they are trying to work with. So a metamaterial designed to reroute microwaves would have cells in the millimeter range, while a metamaterial designed for optics applications would have much smaller cells, around the 380 nm - 780 nm range.
Metamaterials are often associated with nanotechnology because the tiny repeating cell structures used for optics applications are measured in nanometers. Creating metamaterials may require novel fabrication methods, made possible only through nanotechnology. As nanotechnology progresses in the coming decades, it will unlock new metamaterials and lower their cost.
There is at least one known natural metamaterial-- the opal. The opal is composed of cristobalite, a high-temperature polymorph of quartz and tridymite produced in volcanic eruptions. The resulting material is made up of a huge number of tiny mineral cells that are constantly tumbling in relation to another, creating the macro-scale effect of a beautiful display of multiple colors, most prominently a brilliant blue. The research about natural opals and metamaterial qualities are ongoing.