Love the question!
Bit of background: I have been doing operations for almost my entire career and have had some incredible mentors along the way. Most fun 2+ years of my career were spent as a head of ops for an awesome software dev company we grew to 120+ devs (by the time I had to move). It was an honor serving some of the smartest devs in the market.
Here are the points I would consider, when looking for your right-hand-person-in-chief:
- Operations is operations, no matter what industry you are in. I have worked in the entertainment, professional services, legal, software development, and technology consulting industries. Ops is same everywhere. (In ultra-specialized and regulated industries we just surround ourselves with specialists and attorneys.)
- Good COO will be an ultra-generalist. COO should have had as broad of the hands-on experience as possible. IT, HR, accounting, recruiting, infrastructure, marketing, sales, etc.
- Good COO has a good rolodex of suppliers, vendors, and specialists. Instead of "faking it", good ops pro will pick up the phone and ask for advice from an expert.
- Earning credibility with everyone in the organization is very important to the success of the person in this position. COO should be able to speak the "language" of the professional they are talking to.
- COO must understand the delicate balance required to keep employees and customers happy while protecting the company. It is a tough skill to develop and requires passionate drive for sniffing out the facts and mediating outcomes.
- COO has to have a very well controlled ego. Leading by serving is an important attitude.
- Those who chases credit for everything and needs recognition does not fit in any role within operations. Ops is the Secret Service for the company. If ops works well, everything runs smoothly and nobody knows what the heck ops does. If ops messes up, the resulting mess is of tremendous proportions.
- COO will have no qualms getting his/her hands dirty. No white gloves here!
- COO will have backup plans to backup plans and that is how his/her head works ALL the time at work or at home. (E.g. You will not find a good COO who races motorcycles or skydives, because there is only one backup in case of failure).
Just some points for you to think about.
Real operations people are scarce and, more often than mot, many candidates claiming to be ops professionals don't have enough skill to even be an office manager.
2012 UPDATE:
In the last year I have written several articles to clear up misconceptions & myths about startup COOs. I also wanted to clarify what operations people do, since the functional area is much broader than many folks realize.
What do operations people do?
Myths why startups don’t need COOs