I finished the Fade example (http://arduino.cc/en/Tutorial/Fade example) but I don't understand why it belongs to the "Analog I/O" category when actually it uses a digital output:
By the other explanations I know you've got it but here's another way to think about it, comparing the binary to analog worlds. Digital is actually not a very good word to use -by- -itself- on this topic so I'll also use the word binary as appropriate. Digital (typically) means more of a way to 'switch things between specific analog levels.' Binary means 'on or off.'
Humans live in an analog world. That's a given. We may turn a light switch on or off but except for blinding white light or a sealed darkened room we always perceive vision in terms of analog variations of brighter and dimmer.
Most digital based computers live in a binary world. Well, actually at it's lowest transistor and gate levels it's still analog but the -intent- is that they -behave- binarily so we can -work- with them in a binary/digital manner.
Using a PWM pin as an analog output -would- normally mean an -infinitely- variably adjustable output, such as a potentiometer making an LED brighter or darker. However Arduino PWM output doesn't have infinite steps, not even very many really.  But the step increments -are- -small- enough that as the steps change from one to the next the analog-based human eye is happy enough to -perceive- it as an 'analog' increment or decrement in light or sound or whatever the pin is controlling.
The PWM-capable pins are extremely versatile and powerful. They can be used as -digital- to set the volume level of an audio signal to a particular -specific- level. They can be used as analog, by incrementing the register to gradually 'fade' a light from one level to another -as- -if- it were being adjusted by a pot. Or actually they can even be used as binary-digital, by setting a register to 0 or 255 to turn something fully 'on' or 'off.'
So the correct final answer is yes, Virginia, there -is- a Santa Claus, and a PWM pin is -either- digital or analog depending on how you want to use it, or more accurately how you want to think about it for a particular use.
 Example, here's a wikipedia page that demonstrates the analog -effects- of human -perception- of color as regards resolution. Scroll down a bit and on the right side of the screen you'll see a few images of the same picture at different color depths. http://en.wikipedia.org/wiki/Color_depth