Interesting, I just made a pdf with an embedded movie, qt. Very easy to do, I have the CS version and it looks as if only acrobat 6 and reader 6 can understand embedded movies.
Some things to consider before moving towards embedded movies, only works with Acrobat reader 6, does not work with Apple's preview.
Process:
Start with a new PDF doc, I created a bland ai file to start.
Under Tools, select Advanced Editing.
Select the Movie tool, there is also a Sound tool.
Once you have the Movie tool, simply draw out a box and import your movie, if in CS, 6, select embed to embed, it did this be default for me. I imported an iPod commercial, like the dork I am, and ended up with a 1.6 MB pdf.
You can get pretty complex too, making navigation buttons, etc..
Not sure if I see the practical side to this, would rather build a website but it is neat knowing we have this option.