You should shuffle the training data (a set of sequences) when you shuffle the order in which sequences are fed to the RNN, then you should not shuffle the ordering within individual sequences.
Stateless Case:
The network's memory only perseveres for the duration of a sequence. Training on sequence B before sequence A doesn't matter because the network's memory state does not persist across sequences.
Stateful Case:
The network's memory persists across sequences. Here, you cannot blindly shuffle your data and expect optimal results. Sequence A should be fed to the network before sequence B because A comes before B, and we want the network to evaluate sequence B with the memory of what was in sequence A.
For more details on LSTM, study Machine Learning Tutorial, and Machine Learning Online Course.
Hope this answer helps you!