Unfortunately in my experience what you'll quickly find is that video is obnoxiously difficult to manipulate without a lot of cpu power. Let's start from the beginning: how much video do you want?
There are a lot of choices here, but start small. Let's say that, for simplicities sake, you wanted a 640x480 frame of 8-bit black and white video, at 24 frames per second.
That's 640*480 pixels = 307,200 * 8 bits per pixel = 307,200 kilobytes per frame * 24 frames per second = 7,372,800 bytes per second or ~7.37 megabytes per second
So that is a baseline for data throughput for a camera outputting raw frames, and that's not including sound or color. Now you have a few paths you can take: you can start encoding the video stream, or you can get a lot of bandwidth. I don't know the throughput of bluetooth, so I can't help you there.
Encoding unfortunately takes one of three things: a lot of processing power, or specialized hardware, or (possibly) FPGA knowledge that I also don't have. Encoding will reduce bandwidth concerns, but at a pretty hefty cost. You would need to research compression and whatnot to figure out whether you could even get this over your interface and still have the arduino do useful work.
If you want to connect a camera to a microcontroller you'll find that even simply taking stills can be a pain based on how the still frames are delivered. There was a sparkfun camera which gave jpeg frames but didn't have a fixed period for how long the encoding took, and then would suddenly start spitting out the encoded frame as fast as it could, and since the frames were too big to fit in RAM on the microcontroller it had to spend all it's time getting the frame and spitting it out over whatever interface they were using to transmit.
tl;dr: you should establish what you need and probably try and and figure out whether using the microcontroller as the go-between is the best choice.
Good luck! I hope that helps.
TI sells the CC3000 that is very much RTOSless. The stack and everything is on the chip/module, and you just need a driver that's about 6k of code, 3k of RAM (sometimes even less if you're willing to sacrifice throughput).
Last I saw, the Evaluation board which is just CC3000 (or booster pack for launch pad) was going for around $30.
Best Answer
Arduinos are not suited for video streaming at all. Here are some of the reasons:
For those reasons and more, Arduinos and other 8bit MCU's are not able to accomplish what you want. A 32bit ARM processor would be better suited to the task and still very cheap.
Nevertheless here is your answer
If you MUST use an Arduino, the best you could probably accomplish is streaming jpeg at a slow rate. You can add a TTL camera to an Arduino so the Arduino is able to take a picture (there are camera shields that can connect a camera to an Arduino.) The max baud rate on an Arduino is 115200bps (I think) so after a picture is taken it could be saved to a SD card and/or sent via an wireless SD network shield. There is also a Eye-Fi unit that is a SD card that has a built in wireless network.
Keep in mind that this will not be video streaming, at the best it will be streaming a couple low quality pictures a second.
This is what I recommend
The easiest way to stream media from a MCU would be to use a MCU that can run an embedded OS, like the Raspberry Pi. Basically the Raspberry Pi is just like a computer running linux with usb ports etc. And it has the processing power and memory to stream video in real time.
So for your project, you should use a USB camera, like a web cam, and a USB wireless networking adapter (since the RP only has wired network by default.) The OS will handle the networking side of things, all you need to do is to stream the USB video to the network and there is plenty of software and tutorials for that.
They even have a OS specifically made for doing this called XBMC. See How to turn your Raspberry Pi into an XBMC media centre. There is a good amount of documentation on how to stream video from a unit like that, take a look at Streaming Your Webcam w/ Raspberry Pi.
For the software, I personally have used Media Tomb (a UPnP MediaServer) and it works very good. So a search for raspberry pi mediatomb streaming video or raspberry pi media server would probably get you set and going.