With a balun, the frequency response of CAT5 and better will support video up to about VGA or maybe SVGA (XGA and above is pushing it even on CAT5e, but CAT6 may work acceptably over shortish distances). You need the balun, though. Without the balun, the twisted pairs won't do any good, and you'll get lots of extra noise and attenuation, plus it won't be terminated properly resulting in transmission line end effects, which will probably give ghosts.
CAT5 is generally regarded as being "good" to ~100MHz. This means that it has "flatish" frequency response over DC to 100MHz. For VGA, your dot clock is 22-25MHz, so figure 3-4x for good edges on pixels, and you're right at the 100MHz mark. You might see some blurring on sharp edges, but it'll work fine as long as you have a balun.
The balun turns the single ended, 75ohm terminated video signal into a differential, ~100-300ohm signal (check the spec; 100 is right for CAT5, while 300 is more correct for "cheap phone cable", whihc you should not use). It does this using magnetics (i.e. small signal transformers) and possibly a resistive impedance matching network. This results in some loss which, combined with the loss of the cable, limits your range. If you add a video amp to the source end, you can account for this attenuation. You'll see it on a long coax run, too, but the insertion loss of the balun is nonzero and twisted pair tends to be a little more lossy than good coax. This differential signal is what that cable is made for, but you will need a pair for each channel, not just a single wire.
I'm assuming you already have the twisted pair infrastructure here. If you are running wires, go grab however many lines you need worth of RG6. You can use RG59, but it's worth springing for the good stuff unless you're severely budget constrained. Chuck whatever connector you need on both ends (there are RCA and BNC ends for RG6 and RG59) and be done. No need for ugly matching networks like baluns. Image quality over a given range over good coax such as quality RG6 should be comparable to a properly implemented differential link over CAT5 or similar, though the CAT5 cable is cheaper but may require an amp to get acceptable signal levels at the output where coax does not.
You can run whatever you want over CAT5, you just have to make sure you use it properly and the signal is within the limitations of the cable. For analog video, this means keeping it to VGA or lower and using a balun at each end.
rickn: RG58 is 50 ohm. I assume you meant RG59.
Edit: I just noticed that Intersil has an
app note on doing this with active components that is kinda interesting. They pull some neat tricks to back out the frequency response of the cable (the classic inverse filter) to get up to SXGA working.