Donald Wilson, a professor of zoology at the University of Oklahoma and co-author of the 2006 book Learning to Smell: Olfactory Perception from Neurobiology to Behavior, sniffs around for an answer.
In 2004 the Nobel Prize in Physiology or Medicine went to Linda B. Buck and Richard Axel for their research showing that there is a huge family of genes that encode proteins called olfactory receptors. Their findings, published in 1991, opened many doors toward understanding the function of the olfactory system.
One important observation was that individual olfactory sensory neurons typically express just one of those genes. Thus, signals coming from a given neuron provide information about odors that activate the specific receptor protein expressed by that cell. A single receptor protein, however, appears to bind (or recognize) many different odors. Thus, rather than having neurons that respond selectively to coffee or vanilla or Bordeaux, most individual cells (via their receptors) respond to submolecular features of the volatile chemicals coming from those objects. For example, an olfactory sensory receptor neuron may respond to a hydrocarbon chain of a particular length or a specific functional group like an alcohol or aldehyde.
This means that any given sensory neuron will respond to many different odors as long as they share a common feature. The brain (specifically, the olfactory bulb and olfactory cortex) then looks at the combination of sensory neurons activated at any given time and interprets that pattern in the context of previous patterns that have been experienced and other kinds of available information. The interpreted pattern is what you perceive as smell.
Olfactory sensory neurons, which sit in the mucus in the back of the nose and relay data into the brain via axons (fingerlike projections that transmit information out from the cell body), do not live forever. In fact, they are one of the increasingly large number of neuron types that are known to die and be replaced throughout life.
Fortunately, they do not all die at the same time. There are many thousands of olfactory sensory neurons expressing any particular olfactory receptor. When a small subset dies, the pattern of activity that the olfactory processing regions in the brain receives for a specific smell doesn't change very much. In fact, when an olfactory sensory neuron expressing a particular receptor gene dies and a new neuron expressing that same gene matures, the new neuron's axons plug in to the same group of olfactory bulb neurons that its predecessor did. This results in remarkable pattern stability over years, despite continual rewiring.
Let's imagine that on a recent holiday you tried a new wine. The odor (or bouquet, to oenophiles) of that wine is composed of dozens of different volatile chemicals, and each chemical has several submolecular features. Therefore, the wine activates a complex pattern of olfactory sensory neurons by engaging each of their olfactory receptor proteins, which recognize these different features. This pattern is processed and remembered by neural circuits in the olfactory bulb and olfactory cortex.
Several weeks later when you return home, you find the wine in your local market. Despite having replaced at least a subset of the olfactory sensory neurons that first interacted with that wine's unique odor, you are still able to recognize its aroma when you pour a glass, because the overall pattern of activity within the olfactory system remains relatively constant.