Pure nicotine is a yellow colored liquid (although some sources say it's a clear liquid.) "Tar" is a complex sludge that is also yellow-brown. So it's difficult to distinguish 'nicotine stain' from a 'tar stain' based on visual inspection. Let's go to other considerations.
The concept of a 'stain' implies that simple hand washing doesn't remove the coloration. Since nicotine is water miscible, one would expect it's easily removed with soap and water. That implies that either a) a smoker's stain is not primarily nicotine, or b) the nicotine reacts with the skin to create the stain.
Nicotine is sufficiently functionalized that it could conceivably undergo some interesting chemical reactions with proteins, but I don't think that's what's happening. A simple observation is that transdermal nicotine patches do not contain a colored agent, and do not stain the skin. Score one point for the "mostly tar" explanation. Cigarette smoke contains far more tar than nicotine, and tar will deposit on most-any surface (at ambient temperatures), so it's parsimonious to proceed with the "mostly tar" explanation.
The picture shows that the stain occurs on both fingernails and skin. The most abundant protein that's common to those two tissues is keratin. Like other examples of protein staining, the mechanism is complicated and poorly understood, but the basic outline is that parts of keratin are greasy (the non-polar amino acids) that associate with other greasy things. (EDIT: AliceD's answer also depicts the well-known staining of teeth, which are not keratinized, showing that the staining mechanism is likely a nonspecific adsorption of greasy things onto surfaces.)
The stain can be fixed through the involvement of free radicals and other reactive species in cigarette smoke, like formaldehyde. In this sense, reactive oxygen species are active participants. I don't think oxygen deprivation plays a role here. I don't think this can be described as a melanosis, as the skin isn't producing melanin in response to smoking but is simply being coated in tar.
Even if the stain was completely fixed, the coloring would fade away as the exterior skin cells are sloughed off, consistent with normal skin physiology. This is the explanation for the fading of any stained epidermis. The persistence of tar stains on teeth (which do not exfoliate) further evinces that the stain is removed through the replacement of skin cells.