Include art that fits the style of games that the developer makes. If your portfolio is full of bloody monsters and gore you might not have a good shot at a company which makes casual mobile games. Even if an argument can be made that you are capable of other styles, a portfolio full of art that is totally different than the art typically done by the developer doesn't give the appearance that you want to create the art the developer needs. No one wants to hire an artist who would rather be making other types of games.
I see many artists apply to be concept artists that don't really have game concept art in their portfolios. Fine art paintings or magazine illustrations are not as impressive as actual concept art. As previously mentioned, make sure your concept art shows off your artistic ability and also make sure it looks like concept art used in game development.
Stand-alone pieces aren't nearly as impressive as a full set of concept art for a game. A random space marine doesn't demonstrate concepting ability nearly as much as an entire set of characters for a game.
Artists can also go way beyond a complete set of characters. It would be impressive to include concept art for features such as how interchangeable team colors are represented on the characters, or how vehicles look after they take damage. Include concept art for things like environments, weapons, UI and more. Establish a look and feel for the game make sure that everything works well together.
If you really want to get a great job, have more than one full set of concept art in different and visually stunning styles.
In addition to action shots that are great for portraying the mood of a game, include art that would be used in production. For example, concept art of characters in a T-pose from front, side, and back are often needed for 3D modelers. Including this type of art shows that you have the ability to completely design all the details of a character and also demonstrates that you have the ability and understanding that will be needed during development. Drawing a character from the side and front that actually fits together is a specific skill that often needs to be developed.
Show your creativity and understanding of all of the elements that go into game design. A great piece of concept art is only enhanced when a description of how the character will move and be animated is included.
Describe why you have designed the art the way you have, i.e. "The bunnies are all bright blue because they are important and will stand out on the background" or "The facial features of the character are exaggerated because reading the expressions provides vital feedback to the player." These details can really help an art director know how well you understand art for games.
Often in the early stages of game development an "art bible" is created to communicate to everyone working on the game what the final game should look like. Including this type of document can really strengthen a portfolio. This document includes art style information and describes and shows details that are important for capturing the correct look and feel.
This document illustrates information such as: all the characters have large hands; the bad guys have features that are intentionally sharp and pointed, and the good guys' features are all rounded; the shadows are a cool color and have soft edges; reflections in the ice appear slightly distorted.
It's also a big bonus if these elements described in the document appear to be technically achievable and the artist appears to have a handle on the technical feasibility of the concept art. If something would be tricky to pull off and the artist describes the techniques that could be used to achieve the desired look, I would be really impressed. Including this type of document in your portfolio could not only get you a job but also allow you to negotiate a much bigger salary.
Mock-Up Screen Shots
One of the hardest pieces of concept art to create is a screen shot of what the game will actually look like when it is done. An artist who can create a piece of art that looks like a final game (and it's a game everyone wants to play) is incredibly valuable.