If you want to convert your videos, you can use a program like Freemake or Handbrake. I used to use Handbrake, but now I used Freemake. It's easier for non-video techies to use. You should convert to .mp4 video (h.264 video codec, aac audio codec, 29.97 frame rate). You should then be able to use any of the media server channels (like MyMedia or Roksbox) or the USB channel.
Like the other poster said, Plex is also an option. It's a media server channel that transcodes on the fly, so you don't have to convert your videos to watch them. It takes more horse power to run it though.
Roku 1 HD (N1100) / SDTV (Composite) / ATT Uverse 6.0 Mbps / Motorola NVG 510