You're asking a very good question and we understand some aspects of it, but not all of them, nor is there a single comprehensive theory that fully explains all aspects of memory storage and retrieval. But first, one point of clarification, most neurons are not replaced during life. Except for sensory neurons in the olfactory bulb and a sub-set of neurons in the hippocampus, the neurons we have in our brains are the same throughout our lives.

Just to get encoding/decoding out of the way, information the obtain through our sensory receptors is parceled out (primarily through the thalamus and related ganglia) to different regions of our cerebral cortex: vision (occipital lobe), somatosensory (parietal lobe), auditory (temporal lobe), higher cognitive function (frontal lobe), and movement and motor skills (cerebellum). For movement or behavior in general, the individual draws from information saved in these areas.

Now to address your question. In the cortical areas mentioned above, neurons contact other neurons at synapses (the places where neurotransmitters are released from one neuron to another to either increase (excitatory) or decrease (inhibitory) the potential of the second neuron firing. And thus it continues from neuron to neuron. When neurotransmitters repeatedly act in synapse, in addition to causing the post-synaptic neuron to fire, they elicit subtle changes both pre- and post-synaptically. Pre-synaptically, these changes include increases in the number of NT-containing vesicles formed along with enzymatic modifications to increase how much NT is released. Post-synaptically, the numbers of NT receptors increase, as do the numbers of dendrites, and other changes referred to collectively as "post-synaptic densities." Over time and many thousands of times fired, the synapse becomes "stronger" or more able to fire (a model for this is calls it long-term potentiation or LTP).

This is what happens at a single neuronal synapse and it's the fundamental "unit" of memory, however note that each neuron receives input from about 1,000 neurons and provides output to another 1,000 neurons, and there are many, many neurons in the cortices (I don't recall how many, but there's an estimate for the entire brain of 10 to the 11th power that's sometimes mentioned.

Somehow, all of these individual synaptic changes give rise to memories and learned behaviors, but alas, we don't understand the full sequence of how this processing occurs.