Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books.
One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point.
Another approach might be to use an ensemble classifier: you learn multiple weak classifiers, each of which outputs its own prediction at the label, and then to classify any point you run all of the weak classifiers and you take a majority vote of their predictions.
One simplistic method would be to periodically train a new weak classifier and add it to your ensemble. For instance, suppose you have storage for $n$ points. You could add each point to storage as you receive it, then when your storage gets full, train a weak classifier on all $n$ of those points, add it to the ensemble, and clear out your storage.
It might be better to bias your storage strategy towards remembering points that you have classified wrong. For instance, as a simple example, you could reserve $n/3$ storage slots for remembering past points that were misclassified and $2/3$ storage slots for storing the last $2n/3$ points you received. When the latter gets full, you could train a new weak classifier on all of those $n$ points, add it to the ensemble, then classify all $n$ of those points with the ensemble classifier, discard all the ones that were correctly classified by the ensemble classifier, and keep a random sample of size $n/3$ chosen from the remaining points (moving them into the $n/3$ slots for misclassified points and emptying out the $2n/3$ slots for new points).
Finally, you might also be able to adapt boosting methods to an online setting. Boosting methods assign a weight to each training point; the higher the weight, the harder the weak classifier tries to classify that point correctly (i.e., the greater the penalty for misclassifying that point). The idea is that points which have been classified wrong in the past will receive a higher weight, and so future weak classifiers will be biased towards trying to classify those points correctly. Rather than trying to store all training points you've ever seen, I could imagine trying to store a random sample of the training points, where each point is selected with probability proportional to its weight. Thus, you could store $n$ training points and their weights; after you train each new weak classifier, you can update the weights of all $n$ remembered points and then sample $n/2$ of them (say, the $n/2$ with highest weights, or take a random sample with distribution given by the weights).
I don't know how well these methods would work, but you could give them a try in your setting and see. But start by exploring the literature. You know what they say: a week in the computer lab can save you a day in the library.
