Update Thanks to @percusse for pointing out in his comment that the original answer was not the one the OP was asking for.
So I did a little searching and found this link. Basically, the workaround is,
- Install Adobe Reader 9.4.1.
- Install
flashmovie or copy it to your source folder (especially the player_flv_maxi.swf)
Write \includepackage{hyperref} and \includepackage{flashmovie} in your preamble. A minimal working environment would be:
\documentclass{article}
\includepackage{hyperref}
\incldepackage{flashmovie}
\begin{document}
\flashmovie[width=12cm,height=8cm,engine=flv-player,auto=1]{movie.flv}
\end{document}
It seems that, in Linux, you can only get embedded videos in Acrobat with Acrobat version 9.4.1. (Why this is, I don't know yet.) You will also need to install ffmpeg to convert your videos to flv
I downloaded the sample text-flv.tex file from the link. How flashmovie works is summarized in this file.
I can verify the claim of that the movie cannot play on the output pdf on my Adobe Reader with version 9.4.7. Opening the pdf gives a message A 3d data parsing error has ocurred. I can also verify that it works like a charm in Adobe Reader 9.4.1.
BTW, I have TeX version 3.1415926-2.4-1.40.13.
Update: If you are not after embeding First, make sure that you have installed all required packages to run your movie format. You will need to load the package movie15, which comes with TeXLive 2012. The manual says that this package is already obsolete and that you should consider using movie9 instead, which is in ctan but not in TeXLive2012. I used movie15 in this answer.
Try the following MWE:
\documentclass{article}
\usepackage{hyperref}
\usepackage{movie15}
\begin{document}
\begin{figure}[ht]
\includemovie[poster,text={\small(Loading Video...)}]{3cm}{2cm}{movie.mp4}
\end{figure}
\end{document}
The poster option inserts the first frame of the movie. The text option appears before the movie is loaded into your pdf viewer. 3cm and 2cm are the width and height of the frame and movie.mp4 is the name of your movie.
Run pdflatex movie.tex where movie.tex is your tex file. I am using Ubuntu 12.04 and I use evince 3.4 to view the pdf. Just type evince movie.pdf in your terminal. Click on the frame to play the movie. The movie will open with your default movie viewer.
I haven't tried movie9 though.
Update This is in response to User 17791. My previous comment to his answer was deleted when the question was edited by moderator. Here it is, @User17791:
pdfTeX 3.1415926-2.4-1.40.13 (TeX Live 2012)
kpathsea version 6.1.0
Copyright 2012 Peter Breitenlohner (eTeX)/Han The Thanh (pdfTeX).
There is NO warranty. Redistribution of this software is
covered by the terms of both the pdfTeX copyright and
the Lesser GNU General Public License.
For more information about these matters, see the file
named COPYING and the pdfTeX source.
Primary author of pdfTeX: Peter Breitenlohner (eTeX)/Han The Thanh (pdfTeX).
Compiled with libpng 1.5.10; using libpng 1.5.10
Compiled with zlib 1.2.7; using zlib 1.2.7
Compiled with xpdf version 3.03
Below are two snapshots of my desktop with a movie being played in Acrobat 9.4.1. (It's a video of a ritual dance here in Baguio City.)

