As long as they're in the correct file format and have the correct encoding, iTunes should add them in the library. You can drag it into your library or Import it, up to you
Then you can sync it to your iDevice as you wish.
If it's not in the correct format, you can use a converter program to do it and then import the output file the program created into your iTunes library. There are tons of programs to do this and they let you choose the quality. Google "avi to iPhone" and you'll get a bunch of results. They convert all the common file types.
Well they are mp4 files already and I still can't figure it out. Is the correct format just mp4? I can see them in my iTunes library under movies but they're not showing up or syncing. I checked "sync movies" too but still no luck.
I don't need a converter if they are already mp4 right?
I convert all of mine that aren't downloaded through iTunes. In iTunes go to videos tab on the left in your iTunes library and make sure the box next to that video is checked. Then go to "YouriPhone" and to the videos tab for it and make sure the box next to it is checked as well and as sync all videos and then try resync'ing.