While some game companies are excited to have footage used to make videos, and with the popularity of services like Twitch, gaming videos are becoming more common, it can be hard to get permission to use game footage in videos on YouTube.
Step 1: Look at Their PR
Same steps can be used for blogs or about anything you think would need permission for from a movie, book, game, etc. An example is EA and info.EA.com, this is all their press releases. anything found in the press releases on these pages can be used without needing permission.
At the bottom of their press releases, (and most other companies have similar sites) is the contact/PR rep info. You can email and explain what you want to use, why and for whom. This gives you a chance to explain your audience. Be honest and realistic with your descriptions but don't go bashing the company or the game.
Step 2: Tips
If you've done reviews, send examples to show your work and that you know what you're talking about.
Start small: work with a small game company and keep building up up to larger companies with more popular games.
You might be able to get on their press release list. This could be get pre-released games, limited editions, merchandise, news and other stuff. If you take their info and then write a bad review, you could be "blacklisted" or not allowed to use content or game play anymore.
Avoid music in the clips you upload. Game companies often can't authorize the rights to music especially if it is a "real" song like in Dance Dance Revolution, or Guitar Hero.
Avoid Celebrity Voice Overs. Peter Dinklage may have seemed like he didn't care about his voice over in Destiny based on the quality, but you can bet his agent does, and he will want 20% of everything you make off of videos with his voice in them.
Step 3: Expand
You have to remember that PewDiePie didn't get famous overnight. A lot of the things he does are indie games. You have to make a name for yourself before the big guys are going to want to talk to you, or let you try a game that might tank.