<p>I am preparing a project proposal for a client who wants to publish video in his website. I need to define which video formats will be allowed, which video sizes, as well as the necessary tools for conversion and preparation. </p>

<p>I have no experience with embedding video in websites so which markup do I need to play video online?</p>

You could embed them using a flash player, like Youtube for example.
A quick way to do this is using some already made player, like the excellent
JW FLV Player
, free for non-commercial projects and very cheap for commercial ones.
It supports FLV and MP4 video files, you can convert your videos in this formats in a lot of ways, for example using
ffmpegx
.