It would be nice if a link existed from http://arduino.cc/en/Tutorial/BlinkWithoutDelay to http://www.arduino.cc/en/Reference/Millis. That is probably the first place that a person like me will run into a millis(). It took me a bit to figure out what it was about. A simple link would have been handy. :-)
Good idea. Done.
There used to be an example on the reference page, that illustrated how one would actually use millis(). The Arduino team has decided that they wish to have the reference be more terse however, so the example got changed to kind of useless one.