Video on the web is becoming ever more present on regular web sites. There are different formats you can use. Most dominant is the MP4 format, which also has widespread hardware support on PCs and mobile devices.
To be able to start watching a MP4 video without the need to download the whole video, players need to have the appropriate meta-data, also known as the moov atom or movie atom. This is especially true if you are using Flash to play movies. Not all video software put this atom at the beginning of the video file.
FFmpeg comes with a separate tool to do this, called qt-faststart. Windows binaries can be downloaded from http://ffmpeg.zeranoe.com/builds/qt-faststart/.
Example:
qt-faststart old.mp4 new.mp4
With FFmpeg you can also add it to the movflags directly. This isn't done automatically, e.g.:
ffmpeg -i input.mp4 -c:a copy -c:v copy -movflags faststart output.mp4
To see if the moov atom is at the beginning of a video, you can open a text editor and look for "moov" string in the raw output, e.g.:
^@^@^@ ftypisom^@^@^B^@isomiso2avc1mp41^@^Eï moov^@^@^@lmvhd^@^@^@^@^@^@^@^@^@^@^@^@^@^@^
A more detailed explanation can be found on Adobe Developer Connection: Understanding the MPEG-4 movie atom.