This is how I do it.
You will need 2 programs - FRAPS, and some video editing software (I use Windows Movie Maker 2.6, just cause its really simple).
To begin, make sure you save your replay right after the battle ends, before you go to the casualty report screen. As Knowing Crow said, otherwise you will get an invalid file.
Step 1. Open FRAPS, then start Shogun 2.
Step 2. Open your replay. FRAPS lets you record video by pressing F9 (or whatever other button you set it to). With the free version of FRAPS, it goes in 30 second clips (so just keep hitting F9 when it stops). With the full version, it won't limit you at all.
Step 3. If you plan to use FRAPS to record voice, do it with the FRAPS settings. Otherwise, Windows Movie Maker has a great "add narration feature." Start Movie Maker.
Step 4. Go to "import video" (it's on the left side of the movie maker). It will allow you to browse you computer for video. Find the FRAPS video folder, and select the clip you want to import.
Step 5. If you have multiple clips, import them all. Movie Maker will break them into small chucks of 10 or so seconds. Once you have them all done, take the small clips and put them in the storyboard - it is the entire bottom of the Movie Maker screen.
Step 6. Once all the clips are in order, you can add narration (if you havent done so earlier). There is a clearly labelled option to do so.
Step 7. Hit "save movie to computer." This is where you choose what quality you want to save the movie at. I usually put it on the highest quality (still not great) because I have a fast internet connection. *NOTE: This step takes forever, as it has to encode the movie / compress it (dunno the terminology) and it takes a while.
Step 7. Go to youtube, hit upload movie. Find where you saved your Movie Maker movie, and upload it. This shouldn't take too long, unless your speed sucks. Voila, you are done.
This is a really basic description. If you have trouble, search youtube videos showing how to use movie maker or fraps, there are plenty. Good luck!