Here's a little more info about pseudo streaming:
http://flowplayer.org/plugins/stream...streaming.html
It involves installing a script (software) on the server. So yes, in most cases you will have to have a "dedicated server", meaning you are the only one using that physical machine, or at least "virtual dedicated server" which may be shared with other users, but you have a separate section on that server.
Most Web sites are hosted on shared servers and the host will not let you monkey with anything on the server because it might screw up something for other users who also have web sites on that same physical machine.
So VDS would probably be the cheapest, then you still have to install the script yourself... so research that well before you start.
It's a big step moving from progressive downloading and it's low, low cost, to any type of streaming video, pseudo or true streaming. Much more technical and costly.
Video Man