Puzzle:

Using an image editor (Photoshop etc), create a set of black and white images that, if assembled, would form a rectangle that is 655x480. Each of these images will be a mask. Save each as bmp.

Add one of these mask images as an event to a video track. This will "cut the hole".
Add your video to a track just below the mask track. This will "fill the hole".
Make the lower track a compositing child of the mask track above it.
Using track motion on the upper/mask track, set up a move, ending at the "restore" position. You now have one piece of the puzzle flying into place.

Create a pair of tracks as above for each mask element, using the SAME video in the child track. Change the track motion path for each parent mask track. This will allow you to fly the pieces in one at a time.

Other stuff to make this look extra cool:

1) Use a gradient background

2) Add a drop shadow to each mask track, fading out the shadow at the end of the move- this will add some "depth".

3) Add a moving lens flare to each video track, fading out at the end of each move. This will make each puzzle piece appear to have a reflective surface.