How are LSTM's trained for text generation?
You compute the error in the same way as normal - treat the actual output as "ground truth" even if other options are possible. The LSTM will output probabilities of next character, it will not learn to associate a single "true" output except for rare circumstances (such as completing a word that can only be done in one way according to the training data). In practice that means that understanding acceptable loss values in NLP training is different to understanding them in other supervised learning environments, typically being higher than for datasets where ground truth is more predictable from the data.

In this way, it is a lot like a Markov or n-gram model, except that it learns its own internal state representations (they are not prescribed by the model, but are limited by structure and data available). The gated RNN memory models like LSTM and GRU include a mechanism for handling long term memory so can relatively easily learn things like quote, paren pairs etc.


  What I'm getting at is that I don't get how it could LEARN any sort of structure more than a Markov model.


A Markov model can in theory represent any sequence knowledge that an LSTM can. The difference is in terms of efficiency. RNNs have more compact internal representations than explicit state representation in say HMMs. This makes them harder to work with in some ways (it is hard to see what a RNN state vector represents), but means that they can store more complex knowledge about state transitions in less memory. It also means that RNNs can generalise (although not guaranteed correctly) more readily, they will not fall back to random behaviour given a brand new state without any training history.