We have recently covered linear programming and I am comfortable with the weak and strong duality theorems. However, I don't understand what the applications of duality are that are specific to TCS. Mike Spivey's blog post gives some interesting examples of some nice properties of duality but I was wondering if there are algorithmic advances, for example, that come from understanding duality or anything more CS related.
Yup. Everything follows from duality. (I am only half joking). A partial list:
The Hard-Core Lemma
The ability to actually solve LPs efficiently
A large fraction of approximation algorithms results.
To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is essentially equivalent to Von-Neumman's min-max theorem in game theory -- the applications in game theory are also huge). This is essentially what the multiplicative weights algorithm is. See Arora/Hazan/Kale for the best survey on this topic: http://www.satyenkale.com/papers/mw-survey.pdf
Perhaps the most famous application of duality has been the max-flow min-cut theorem (introduced in Ford & Fulkerson's landmark paper "Maximal Flow Through a Network"). The theorem states, formally, that the optimal solution for the (primal) integer linear program for finding the maximum flow is equal to the same optimal solution for the dual program to find a minimum cut.
The wikipedia page provides a good summary of this concept; http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Moreover, this special case of LP duality has been previously studied in a graph-theoretic context, in the form of Menger's Theorem and Konig's Theorem. Menger's Theorem characterizes the number of edge-disjoint paths between vertices $x,y \in V$, and Konig's Theorem states the equivalence between optimal solutions for maximum matching and minimum vertex cover on bipartite graphs (one can find a nice reduction to flows).