Here's my approach (right or wrong, its what I do):
*A I try to find a setting in the output dropdown that gives me the following encoding options:
*B Pick MPEG-4 (if you need to revert back to MPEG-2 That should still work, just make sure that you go the extra step in the Audio Codec section below this section and set it to mp3 - hint if I am also rendering out sound I set this anyway).
*C I personally try to use the H.264 codec, that does NOT imply that you should, its just what I do. To get a better sense of the codecs, and their respective containers, I recommend looking at to place in the manual.
*OUTPUT Whatever combination I pick (If I'm still unsure about it), I can see if it is going to work or not, by hard-coding the file extension of my desire, cross my fingers, and render. Sometimes I will get a default extension like *.dvd; sometimes my first extension may not work (such as *.mp4), so I try *.mpg, *.mpeg, etc...
The process seems pretty effective for me.
I will recommend this:
Try to stay away from getting lost in codec availability for your OS for now, as that is a huge topic, and you may even get lost in it. Your Blender implementation of it can probably be solved a lot quicker.