The dyeing or staining of gemstones is one of the oldest gem treatments. Somewhat porous gemstones, such as polycrystalline varieties, allow pigments to penetrate the material to a certain extent. Monocrystalline gemstones can be coated with a dye or colored by a pigment which penetrates the stone along fractures. Where fractures aren't present naturally, they can be introduced by heating the gemstone and cooling it suddenly thereby quench crackling the stone. All of the above methods are described in ancient texts, leaving no doubt that these practices have been around for several thousands of years.
The detection of a dye isn't too difficult in most cases. Optical inspection with the aid of a loupe or microscope often reveals color concentrations in cracks or surface irregularities. Keep in mind that not the whole gemstone needs to be dyed in order to enhance its color. Just the pavilion, girdle or culet can be stained, improving the color of a stone throughout due to internal reflections. A blue dot on the culet of a yellowish diamond, for instance, will make the whole stone appear more colorless.
Historically stones were dyed using organic substances which deteriorate over time. Currently more stable inorganic pigments are used. Most dyes can also be detected by running a swab moistened with acetone over the stone: some of the dye will be dissolved and will be visible on the swab.