If you are streaming to the 360 -- using Media Center, TVersity, etc etc -- then your PC is doing all the work and you must have the appropriate codecs installed on the PC.
If you are accessing files through the "Video" option on the Media blade, then the 360 is doing all the processing and you'll need whatever codecs/updates MS has released for the 360. As faston said, this should happen the first time you play a file that needs an updated codec, although you may be able to find them in the Marketplace (I know I found some sort of Apple/iPod audio update there, but that may be treated differently).
So far I've stayed away from streaming. I tried Orb quite a long time ago with disastrous results, so I've settled with just (re-encoding when necessary and) sharing the files via WMP11. I've heard really good things about TVersity lately though so I may give that a try.
Sony KDL-52EX700, Toshiba HD-D3, Motorola DCT-6416, Popcorn Hour A-110, XBOX 360 w/HD-DVD