Unless your community has explosive growth from the start, you'll be starting with a community size that can be moderated by a very small team (possibly just you). However, since you likely don't want to monitor user interactions 24 hours a day, 7 days a week, you are going to want some kind of help.
Are you working with others to build this community from scratch? Another who shares your passion for the game and shares your goals for the community is a good candidate. Someone who put in time and effort to work with you to build the web site, set up the message forums, chat rooms, and game servers likely has made an impression of some kind on you. If you trust them to build all of this with you, I believe you'd trust them to help out with moderation tasks during the early stages of the community.
After the initial moderators that worked with you to bootstrap the community are in place, you and your team need to determine future moderation goals. Are you going to have elections that the community (or subset of the community) can decide on? Are you and your team going to appoint new moderators? These are both valid options, but require different things from you.
For a community election, you want to set up criteria that will ensure you get a good set of candidates. The goal is to prevent it from being only a popularity contest. While popularity is a huge factor in this method of selecting a new moderator, there can be objective criteria that are important too. Stack Exchange has such criteria (reputation, badges, lack of suspensions) to be eligible.
If you are appointing moderators, the criteria set out above may be less formal, but it's still important to have a benchmark. You don't want to appoint the new player that joined two months ago that everyone knows just yet. They may be very enthusiastic, but do they know your community well after only two months?
In my community, I strive to have moderators available almost 24 hours day. My player-base is global. It's unhelpful to users twelve time zones away from me, if a troll joins a game, and I'm sitting in the office working without such coverage. When appointing such users, you may need to depend on the community for feedback. Hopefully, you're staying engaged and users talk to you. If so, you'll be hearing things about players in the community that step up and confront trolls or will helpfully report them to you another way. There will be users that lead small minigames on the servers (because there are always times when a dance off starts before a round starts, or everyone is going to rush, or instead of guns we're going to play a round with melee weapons only, etc). It happens and if other players enjoy these short diversions from the normal play style, you'll hear about it and about who led it.
Each community has a set of criteria that are important to them. In my game community we have a few things that must be met before we'd consider anyone for a moderator position.
- Maturity on all platforms of the community. This means that even in the heat of a game, they aren't jerks that make kids cry or other players leave because it's just not fun. It means that the user can express their thoughts on the forum and chat server in a mature way. It's also important to remember that maturity does not mean users are a certain age. Age is related to maturity, but it does not equal maturity. I'm met very mature young teenagers and very immature older players.
- Use can express disagreement in a constructive way. I don't want all of my moderators to agree with me all of the time. That doesn't help the community grow. But, I don't want moderators that attempt to undermine the administration team because they disagree with a decision. If they disagree, we have a variety of ways they can let us know. It's important to me that moderators know how to use those tools. It's also important they they can accept decisions they disagree with. If, after making their disagreement know, the administration decides to change nothing, the user needs to be able to handle that.
- Knowledge of the community and helpfulness in relaying that knowledge. A moderator should know about the community they are going to be a leader in. If someone asks a question about the community, they should be able to either answer the question or know who to get the information.