How does this method differ from the experience replay, as they both use past information in the training? What's the typical application of both techniques?
Using a recurrent neural network is one way for an agent to build a model of hidden or unobserved state in order to improve its predictions when direct observations do not give enough information, but a history of observations might give better information. Another way is to learn a Hidden Markov model. Both of these approaches build an internal representation that is effectively considered part of the state when making a decision by the agent. They are a way to approach solving POMDPs.
You can consider using individual frame images from Atari games as state as a POMDP, because each individual frame does not contain information about velocity. Velocity of objects in play is an important concept in many video games. By formulating the problem as a POMDP with individual image inputs, this challenges the agent to find some representation of velocity (or something similar conceptually) from a sequence of images. Technically a NN may also do this using fixed inputs of 4 frames at a time (as per the original DQN Atari paper), but in that case the designers have deliberately "solved" the partially observable part of the problem for the agent in advance, by selecting a better state representation from the start.
Experience replay solves some different problems:
Efficient use of experience, by learning repeatedly from observed transitions. This is important when the agent needs to use a low learning rate, as it does when the environment has stochastic elements or when the agent includes a complex non-linear function approximator like a neural network.
De-correlating samples to avoid problems with function approximators that work best with i.i.d. data. If you didn't effectively shuffle the dataset, the correlations between each time step could cause significant issues with a feed-forward neural network.
These two issues are important to learning stability for neural networks in DQN. Without experience replay, often Q-learning with neural networks will fail to converge at all.
Can they work together?
Sort of, but not quite directly, because LSTM requires input of multiple related time steps at once, as opposed to randomly sampled individual time steps. However, you could keep a history of longer trajectories, and sample sections from it for the history in order to train a LSTM. This would still achieve the goal of using experience efficiently. Depending on the LSTM architecture, you may need to sample quite long trajectories or even complete episodes in order to do this.
From comments by Muppet, it seems that is even possible to sample more randomly with individual steps by saving LSTM state. For instance, there is a paper "Deep reinforcement learning for time series: playing idealized trading games" where the authors get a working system doing this. I have no experience of this approach myself, and there are theoretical reasons why this may not work in all cases, but it is an option.
If they can work together, does it mean that the state is no longer a single state but a set of contiguous states?
Not really, the state at any time step is still a single state representation, is separate conceptually from an observation, and is separate conceptually from a trajectory or sequence of states used to train a RNN (other RL approaches such as TD($\lambda$) also require longer trajectories). Using an LSTM implies you have hidden state on each time step (compared to what you are able to observe), and that you hope the LSTM will discover a way to represent it.
One way to think of this is that the state is the current observation, plus a summary of observation history. The original Atari DQN paper simply used the previous three observations hard-coded as this "summary", which appeared to capture enough information to make predicting value functions reliable.
The LSTM approach is partly of interest, because it does not rely on human input to decide how to construct state from the observations, but discovers this by itself. One key goal of deep learning is designs and architectures that are much less dependent on human interpretations of the problem (typically these use feature engineering to assist in learning process). An agent that can work directly from raw observations has solved more of the problem by itself without injection of knowledge by the engineers that built it.