What are good references on understanding online learning?
Most online learning algorithms come from at least one out of these lineages:


the perceptron

State of the art perceptrons are the passive-aggressive algorithm, the structured perceptron, and their many varieties.
The winnow 

The winnow has been reformulated as exponentiated gradient methods, and can be applied to structured problems as well. There are also varieties that deal directly with L1 regularization (to guarantee sparsity), such as SMIDAS.
Stochastic gradient descent

Stochastic gradient descent is when you apply online optimization to a possibly batch problem. State of the art algorithms are Leon Bottou's LaSVM, Pegasos, and many neural network algorithms can be easily trained in this setting. See the theano tutorial for many examples. Maybe online EM fits here.
particle filtering

This is also known as rao-blackwellized inference, and it allows you to update a graphical/probabilistic model as more data arrives. Some good examples are online topic models and the NIPS tutorial on SMC.


There are also some broader issues with online learning, like online-to-batch conversion, budget techniques for online learning with kernels (like this paper, this paper, and this paper), many different flavors of generalization bounds, sparsity concerns (and also the SMIDAS paper I cited above), hashing to save memory, and many other issues.