Here's a new way to embed MP4 videos, instead of uploading to youtube; upload the MP4 via the "Upload Attachment" tab, then right-click the file and "copy link address" or similar option from the menu. Then include that address between [ video ] and [ /video ] tags (without the spaces). You should get an embedded video player of the video in your post. I'll look at extending this to AVI and other formats soon.
Update: see below about optimising the video for the web - and consequently enabling "instant start" playback.