The night that your statement drops. If the date on your statement is 2/12/2011, they'll send in the info late in the evening on 2/12. This is not the due date; it's the date up in the corner of your statement (or wherever.)
Experian generally puts the new numbers on your report that night or the next day. Equifax and TransUnion generally take 3-5 days, sometimes longer, to do so.
Discover CSR's will enthusiastically tell you that they update every Friday. They're wrong. 
(However, Discover has been known to do an extra, random update during a cycle. No one knows why, including Discover when it happened to me and I called. It's not common, though.)