@op
1. First decide which encoding algorithm to use: H.264, Xvid , VP8, theora etc. I would suggest h.264(a.k.a mp4).
2. Video quality depends a LOT on the encoding settings used. Now, there generally two kinds of encoder
a) Those that let you select only from a set of preset and lets you to play with only a few encoding settings.
AND
b) Those that supports all or most of the encoding settings an algorithm supports.
Most of the people talk a lot about some of the apps that come under category 'a'. But believe me those apps all suck.
Apps that come under 'b' are:
a) Handbrake -- supports only h.264, its free, cross platform, very stable and its awesome.
b) MeGUI -- supports h.264, Xvid and many others, only for windows, a bit complicated.
c) Staxrip.
d) Avidemux -- supports h.264, Xvid, h.263(old 3gp etc), theora, vp8, not just an encoder can do many others things, cross platform, very good.
e) Tencoder.
f) ffmpeg -- command line tool, supports h.264, Xvid, theora, vp8, h.263 and many more, cross platform, stable, most complete, most powerful, free, nifty little tool thats called the swiss army knife of video processing, can do cut,merge,capture,encode,broadcast,apply filter,extract audio and many many more. Its the BEST.
If you decide to encode in h.264(and as I guess you are new in encoding) I would suggest go for Handbrake. Its the most easy to use h.264 encoder. Once you understand all the options and what they mean, you can try MeGUI. But now, the sheer number of features and options of MeGUI will overhelm you.
3. Select the set of options that serves you best.
This part isn't that easy. I would say, cut a very good quality 1-2 minute video from a movie, convert it with different settings and check the quality and size of the result. You will soon hit the set of settings most acceptable to you.
Tips:
1> Resize the video if necessary. Means, like to play the video on less capable devices like netbook, droid, PMPs etc, its better to resize a movie thats 1080p(1920x1080) to 720p(1280x720) or less. Be sure to keep aspect ratio the same. Resizing can decrease the size a lot.
2> Two pass encoding generally produces better result but takes more time.
3> Always enable 8x8 transform when encoding in h.264. It is the single most important option in h.264 to increase compression ratio.
MYTHBUSTERS:
1. Formatshit is better than Handbrake, Avidemux etc.
NO. It can't be. If you say so you know nothing. There are two most popular standards, Xvid and h.264. And, there are a few software implementation of h264 encoders(I am saying 'software implementation' cause, there are hardware implementation too). Among them, x264, made by same folks who made VLC player, is the best.
Now, most free and non-free encoder apps like Handbrake, ffmpeg, MeGUI, formatcrap etc use x264 inside them. Which means, these apps are only just fronends to x264. So, as long as an app lets you fiddle with all the options that x264 supports, it cant be any worse than x264.
2. This and this paid apps are better than free apps like handbrake, ffmpeg, megui etc.
NO. Read above.
3. Handbrake and meGUI are bad. Formatcrap is good cause it gives better quality.
NO. Read above. Also, quality and encoding speed depends heavily on the encoding settings. You supply appropriate options to Handbrake(or any encoder, per se) it will surely beat formatcrap.
4. Cyberlink total.... and xilisoft... are better and faster cause they support GPU encoding.
NO, they are just two piece of craps. Don't even bother to pirate them. But yes, theortically GPU acclerated encoding should be faster. But you have to wait a few years for that.