Online approximation algorithm for median?
If you need the exact median, store the last $k$ elements in a self-balancing binary search tree.  Also keep a linked list of the last $k$ elements.  At each time step you can delete the oldest element (the list will tell you which one) from the tree, then insert the newest one into the tree.  It is easy to obtain the median from the tree in $O(\log k)$ time.  Thus, you will do $O(\log k)$ work at each time step, and you will need $k$ space.
If you want to use much less than $k$ space, and are satisfied with the approximate median (you don't need the exact value), you can use various methods for approximating a streaming histogram.