Firstly, I'd like to emphasize that the understanding of memories and learning as we know it is still in its very early stages. In fact, the mechanisms behind short-term memory are still under intense debate.
As for long-term memory, it is essentially caused by chemical changes in synapses between neurons in the brain. When you sense stimuli from your environment, action potentials follow a specific trail of afferent neurons towards the central nervous system, which then sends a message back through efferent neurons to initiate a response. The high frequency of these action potentials from the same stimuli of whichever sense allows for the strengthening of specific connections between neurons, which is called long-term potentiation. This phenomenon is one of the major components of synaptic plasticity, which also applies to the weakening of synaptic connections between neurons due to lack of transmission, as well as the change in the number of connections the neurons are receiving and making. Synaptic plasticity is also influenced by the change in quantities of neurotransmitters being expulsed into the synaptic cleft, and how cells react to these neurotransmitters, which is highly regulated by calcium levels. Ultimately, synaptic plasticity in accordance with learning is referred to as Hebbian theory.
We are still not exactly sure where memories are stored within the brain, but we do know that the hippocampus does play a big part. It definitely aids in the storing and structuring of memories in the form of these millions of synaptic changes. Finally, memory consolidation occurring in others regions of the brain over longer periods of time is likely, but still debated by some.