Resolution is one factor (a 1080p "high def" video will take much more space than a 480p "standard def" one..).
Another is compressibility. Without going into too much technical detail, some videos lend themselves much better to compression than others.
Another is quality (different from resolution). Again, not too much detail - but all current video coding is lossy - meaning after compression, what you get out is not the same as what you put in (same thing with mp3 music files).