When I host videos I do it as a pseudo-streaming or progressive download (same thing) rather than true streaming. This should allow the user to begin watching the video before they have downloaded the whole thing. Additionally it should allow the user to skip ahead to any area of the video and begin play back there regardless of whether it has buffered there or not.
There are several ways to accomplish this, uploading to You Tube being the easiest. If you don't wish to go the YouTube route, there are several ways you can go. HTML5 is coming out and includes new features to deal with video. By encoding the video into h264 and Theora you should be able to reach most modern browsers with use of the Video tag. The disadvantage being that if they do not have HTML5 support in their browser they won't see the video. Also since the official codec of HTML5 hasn't been decided yet, you will have to keep several copies of the video around in different formats to ensure wide support.
Another option is to go the flash route. This is currently the recommended way as almost everyone already has flash. You can encode your videos to .flv and it should be straight forward to get playback out of them. I don't know if progressive download will work "out of the box" with this approach but it should be easy to get it working.
Also you can do it the way I do it. I had already encoded a large amount of video encoded with the h264 codec for use on my Ipod. In order to stream this I had to install a module in Apache (available for Lighttpd and Ngin as well). Its called the H264 Streaming Module and is available here
http://h264.code-shop.com/trac/wiki. With this and properly encoded video you should be able to set up pseudo streaming flash video. This is obviously a more complicated way of doing things and I only mention it because it is a stepping stone to the "ideal" solution.
The "ideal" way of doing things in my view, would be to set up HTML 5 video with use of the video tag and set up flash to activate as a back up in case their browser dose not support HTML 5. This would hopefully allow you to show video the largest possible audience including any device with flash or HTML5 support. This is important because a lot of smart phones do not support flash but do support HTML5.
I have just given a brief overview of the subject. There are countless other ways of streaming video, but these ways seem to be the most common or have the largest advantages. If you have any questions about setting up one of these solutions let me know and I can try to give you more details.
Also there is the matter of a front end for your video. If you go the you-tube route I believe they provide you with one. If not I highly recommend JW player(
http://www.longtailvideo.com/) It supports a wide range of formats and has a clean functional interface.
