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 3 (4230) / 42" Sharp LED 1080p HDTV / RadioShack Amplified Indoor Antenna
Roku HD (N1100) / 25" Sharp SDTV / GE Indoor Antenna
ATT Uverse 6.0 Mbps / Motorola NVG510 Gateway