I have never done any paid work as a pixel artist before, but if I were to look for a pixel artist to hire, FROM a viewpoint of a company that I assume is looking for one primary artist to handle/all most of the art-related work, I would consider the following:
Style/Adaptability - Some people have very unique styles, and if you hire someone with a unique style, that is probably very likely what they will more or less create things with this style. I think those people with very defined styles are less used to drawing out of their comfort zone as well, which is why the style is so defined. Of course there are just as many artists without a style label on them, and they will try to change up their workflow and drawing habits to suit the game's needs.
Variance - Another thing I would value highly in an artist is their ability to draw different subject matter. What I mean is, they should be experienced and knowledgeable about drawing sprites, being able to animate them, interface design, backgrounds, concept art, etc. If you're looking for someone to fill a lot of roles, this is very important.
Speed - On the professional level, I think speed is almost as important as quality, if you're looking for a good artist. They need to be able to effectively use shortcuts in their program of choice, and probably know quick ways to get things done that would otherwise take a long time. Just general fastness and not having to redraw something 50 times before it's correct is good too. (As an MS Paint pixel artist.. I would recommend not hiring anyone that uses it primarily for their pixel art.)
Knowledge/Experience - A basic one. Not just knowledge about art either, but about games as well. I would probably hire a less skilled artist that has worked on several games before rather than a more skilled artist that has no experience at all. This is not to say you shouldn't give newcomers a chance. I would ask for a sample to be drawn first, maybe impose a time limit of some sort so you can make judgements based on that.
An artist that has experience outside of pixel art, being able to paint traditionally or digitally or use vector art, etc would be huge pluses in my book as well. At least, in your case it seems like you are looking for a single person for all your artistic needs, then it seems like it would be necessary to find an artist with talents in many styles and mediums.
However, I have not done any professional work or anything like that, so you may want to take this with a grain of salt. There are many more experienced artists and game developers here, that will probably show up to disagree with everything I've mentioned.
(I reread your post, and I understand you say you are looking for a sprite artist specifically, however I'm going to leave what I wrote, because it does seem you may not have someone to fulfill the many different artistic requirements a professional gaming company should have, that go way beyond spriting.)
