Yeah, this stuff confuses me a bit, too, but in my (probably wrong) understanding, mp4 is the codec itself—meaning a type of container that determines how the contents within are to be interpreted.
Unfortunately, no one codec is supported by all browsers / devices, so if you choose just one format, some people will miss out. There are some nice tools for converting video into various formats, like Miro, but you are still going to have a lot of work on your hands if you are going to update the content regularly.
Short of doing all this converting, you can just put a link on your page to the file and let people deal with it as best they can, or your could put it in a <video> element and likewise let people sink or swim, depending on their device. YouTube is certainly an easy way around all this, as it automatically converts the video to the various required formats.
I've found http://www.longtailvideo.com/players which seems to be setup to allow streaming of MP4. I need to test in a full range of browsers but in my quick test of modern browsers it seems to work ok.