Your biggest goal in hiring a sysadmin should be to avoid a charlatan. A sysadmin's work product is a set of interacting systems that isn't falling apart, which can be accomplished by never touching it, or by being good at your job, so a charlatan can skate without ever really having to touch anything for some months if they try hard to avoid having to actually do anything. When pushed, however, they will fail, and you're stuck with broken shit to fix.
Think of a developer who fails to check in their code for the first couple months on the job: is it a simple case of bad/anti-social coding practices, or are they hiding the fact that they suck? Sysadmins are in a similar position, except there's rarely ever the degree of change control there is for coding. Systems programming tools like puppet are good for fixing this because (if they are used as the only means of systems administration) they can treat the system configuration as a software project, and you use all the same auditing tools you would with coders (e.g. commits mails).
In my experience, certs are irrelevant at best, and misleading at worst. Never, ever, ever hire someone based on the strengths of their certifications. Of all the resumes I've seen, the best technical people do not stick cert logos, when they have them, on a resume---it's a big dangling sign that someone is depending more on their pedigree than their actual skills. Written-test certs are multiple-guess questions based on specific verbiage from the textbook they are based off of. I'm confident that I understand RFC4601, have designed and implemented a secure, global, interdomain multicast system, and got a 67% the last time I took a CCNA practice exam. Meanwhile, my second-level-certified subordinate can't grok that there's no functional difference between RFC1918 and public addresses...
Contrary to what others have said, longer resumes are better than shorter ones: they give you more specific questions to research and ask in the attempt to dodge charlatans. Do multi-level phone interviews if you have to: use the first one to tease out what they were actually doing, and the second one after you've figured out what the right questions to ask for the given technologies are.
Your second biggest goal should be to find someone who's got experience on systems you're using already. Find someone who has dealt with the issues that you are experiencing now or can forsee experiencing in the future (build systems and deployment methods, monitoring systems, security, scaling). Look to hire someone who has worked in similar business situations to what you have now, and is prepared to deal with the problems inherent in your situation. An engineer with an MS in networking who's used to having an unlimited budget, purchasing department, and year-long project cycles is not going to work out in a startup. Conversely, the Linux anarchist isn't going to fare well when he's asked to suffer the ActiveDirectory change-control procedure in your Fortune 50.
If you need to build a department as you grow, don't hire someone who hasn't hired anyone before; if you need to deal with 20TB of highly available data, don't hire someone who hasn't used a SAN before, etc.