Gems are a product (or by-product) of mining. There are six known types -- diamond, emerald, quartz, ruby, sapphire, and topaz -- with quartz being by far the most common.
An individual mine produces one type of gem, but the gems can be of any size. Mines seem to produce gems randomly in a ratio of 1:7:49:343 for huge:large:medium:small. (I was getting a ration of 0:0:1:2 on my mine -- Oofafwet)
Gem pockets come in 40x40 coordinate squares. In effect, this means if you cross a multiple of 40 in either the X or Y axis, you're in a different gem pocket, and might get a different kind of gem if you place a mine there.
Occasionally, these gems also are produced by Water Mines.