I think the icon will change depending on which application you set the file to open with. For example, setting .avi to open in Quicktime, will have the 'Q' logo on the icon. Setting it to open in Mplayer will have an mplayer icon.
You'll find the icons for each file type within the Package Contents of each application. So, if you're using Quicktime, right click the application and choose Open Package Contents. Navigate to the resources folder and in there will be the icon files.
I suggest you make a backup first of all these icons.
Your next step is to replace these icons with the new ones. You'll need to ensure that the names are exactly the same, as Finder/Quicktime will be searching for these filenames within this location.
If you've downloaded the icons as a set, they are usually named correctly. If they're ones you've made, cross check to make sure they match up. Then, just drag the new icons into the resources folder, choose Replace and you should be all set.
If you're using multiple movie players, you should probably do this for all of them if you want a common icon regardless of what you open the file with.