Good game trailers, in my opinion, are a dead art. These days, Developers/publishers opt to show flashy cutscenes from their game over the actual gameplay, which is 100x more important. An example is Dead Island's trailer. It had everyone in a frenzy, and people thought it would be an incredible game based on the trailer, which was basically all one big cutscene. In the end though? The impression I got from everyone who hyped it up was that the trailer kind of mislead them. The game wasn't bad, but not nearly what they thought it would be either.
What I take from that is that you should be more up-front with your target audience (Whoever that may be) and show more gameplay than cutscenes. There's nothing wrong with sticking story elements and cutscenes in here and there, but gameplay should be the most important thing.
And going back to your target audience, you need to show them in this trailer your biggest selling point (Which of course would have to be in gameplay); that thing which will separate it from every other game in the genre. If you were making a platformer for example, you'd want to show them why this game isn't another Mario game with slight differences.
Also, if you're looking for something to record with, I recommend FRAPS, but not the free version. The free version always creates bloated video sizes and can only record for 30 seconds at a time. The paid version (Which is pretty cheap from what I remember) doesn't have those problems.