http://www.youtube.com/watch?v=4cPWCaRWe0w&search=invisible%20skateboard
How is this done?

The skate boards might be entirely green/blue, and then removed using Chromakey. Then the footage with the board missing might have been placed on top of footage without any skateboarder in it at all.

Any immediate shadow under their feet could be added as well with effects software.

What a great little video - I'm still smiling...

I doubt chromakey would have worked for this. Probably painstaking rotoscoping. And considering that the camera moves all the time, I don't think the clean matte was from another shot, but rather from parts of the same shot. I've done something like this before (though it wasn't anywhere as complicated). It's too bad the compression is so high; I don't know if the effect would look clean in uncompressed video.

This is a segment from a video/movie called "YEAH RIGHT!" directed by Spike Jonze.
Some info at Amazon:
http://www.amazon.com/gp/product/B00015YWAS/103-5766046-4067051?v=glance&n=130

The boards were painted green to facilitate keying ... some roto was surely used as well ... and the camera was on a motion control rig, so they could get a clean plate take to put in place of the boards. (the motion control rig makes the replacement pretty routine... just a key + roto to matte out the board & shadow)

Interesting.

It's got a really raw, almost handheld feel to the camera movement, which didn't look like any motion control was used. It makes it all the more impressive that one was used.

which didn't look like any motion control was used.

I never figured that any motion control rig was used either, but it makes a lot more sense to me knowing so. Otherwise, that would have been a 'lot' of work in the post.

Actually, they may have used something like MOKEY which can essentially automate the roto process, remove the skateboards and automatically fill in the background. Check it out at http://www.mokey.com/