How do you plan to present the videos? What format are they in?
You can imbed youtube and other online streaming services videos with a number of plugins relatively easily. They can be placed either into page or post, or into a widget – which, depending on your theme may appear in a number of places. For this i use ‘wordpress video plugin’.
If you are planning on hosting the video on your own server, and streaming it from there — i am no expert in flash streaming but I think you need a certain type of webhosting which can convert the files to .flv, unless you do that on your own computer and upload the .flv files. I have not attempted to do this myself, but i assume there would be .flv player plugins out there for wordpress.