Should You Hire A COO?
10 years ago, if you were the founder of a high-growth company it was reasonably likely that your investors would want to bring in "adult supervision" as CEO to run your company. This has shifted more recently with a slate of COO hirings following the example set by Facebook with the successful run of Sheryl Sandberg.
Box, Facebook, Foursquare, Stripe, Square, Twitter and Yelp are all companies that chose to hire a COO as a complement to the founders, rather than replace the CEO with a "grey haired professional operator".
Why A COO?
A COO is not about the title, but rather the background and experience you are looking for. Optimally, you want someone who will come in to complement, operationalize and execute your vision as a founder. Many technical or product focused founders want to (and should) remain focused on the product and overall market strategy. In parallel the COO would build out and manage areas that the founders lack bandwidth, interest or experience in. E.g.:
Add executive bandwidth and a business partner for technical or product focused founders.
Scaling the company. High growth companies have special needs around scaling and implementing simple processes (e.g. recruiting infrastructure, corporate governance, etc).
Build out executive team and organizational scaffold. Hire executives or teams for areas founders don't understand well e.g. finance, accounting, and sales. Help in screening and hiring executives for product, engineering, marketing as well.
Take on the areas founders don't have time for, are poorly suited for, or don't want to focus on. Ongoing management of the "business side" (corporate development/M&A, business development, sales, HR, recruiting, etc.) while the founders continue to focus on product, design, and engineering - e.g. Mark Zuckerberg's focus on product at Facebook.
Shape the culture for the next phase of the company's life. Sheryl Sandberg has impacted how Facebook is run across the entire organization by, for example, bringing a culture of people development and managerial excellence.
Why Not A COO?
All growing companies need to build out an executive team and the ability and expertise to scale. This can be done via hiring or promoting a set of people who in their sum complement the founders and allow the company to scale rapidly and effectively. It is not necessary that one of these team members have the "COO" title. For example, at Polyvore the CFO owns multiple areas beyond traditional finance.
Additionally, the COO title sets a very high bar for the person. You can't really hire above them later like you could with a VP, taking flexibility out of future organizational evolution and changes as the company goes from e.g. 100 to 5000 people. If the COO is out of their depth they often won't accept demotion to VP and will leave instead.
Another option raised by Reid Hoffman is to replace yourself as CEO instead.
How Do You Choose A COO?
For COO you optimally want someone strong enough to be CEO of a company or with solid general management or key functional experience. For example Sheryl Sandberg interviewed for other CEO roles before accepting COO of Facebook. Similarly, Box's COO Dan Levin was a CEO or President of 2 companies and a GM at Intuit before joining Box. You want someone so excited by your company's vision and opportunity that they are willing to give up some of the perceived upside of being a general manager or CEO elsewhere to join your company.
Criteria to look for are:
Seasoned executive willing to suppress their own ego to partner with, and execute, a founder's vision.
Chemistry with founders.
Past experience scaling a company or organization.
Entrepreneurial. Optimally, you want someone who has both operated at scale, as well as has startup experience (or scaled something from scratch at a larger company).
Functional expertise. They should have previously run (at another company) a reasonable subset of the functions you want them to own initially at your company.
Ability to hire. They will be building out a chunk of your company's organizational skeleton. You need someone who can hire well and manage executives themselves.
Someone you can learn from. Optimally as a first time founder or manager the COO can teach you about management or other areas.
Process focus. Bring lightweight processes or best practices from other companies, and be smart about how to tailor the necessary ones for use by your company. Sheryl Sandberg did this in many ways at FB.
When hiring the COO, you should have a clear sense of what you want to keep as founder (e.g. design, product, marketing, engineering) and what you are willing to truly delegate (e.g. BD, sales, Corporate Development, finance, HR, operations, etc.). Otherwise you may not set the situation up for success to being with.
I don't think every company needs a COO. Rather, a well rounded executive or leadership team allows you to do without one. However, if you do decide to hire a COO the criteria above may be of use.
 The original title for the Foursquare COOs was "general manager".
 Twitter has recently re-added the COO role after a period without one. The original COO, Dick Costolo was promoted from COO to CEO.
 Other interesting early examples include Microsoft, where Bill Gates in the 1980s had seasoned "Presidents" working for him, and Oracle, where Larry Ellison has gone through various COOs over the years. Gates, of course, only brought in venture money after Microsoft was profitable, so he had sufficient control of the company to not worry about being replaced.
 Extra thanks to Aaron for tons of helpful comments and ideas which I shamelessly ripped off for this post; e.g. the first part of note  above.
You can follow me on Twitter here.
How To Hire Great Business Development People
How To Choose A Co-Founder
How To Choose A Board Member
When And How To Fire An Employee At An Early Stage Startup
How To Fire A Co-Founder
Never Ever Compromise On Culture Fit
Hire For the Ability To Get Shit Done
Hiring Criteria For Your First 5 Employees
5 Myths To Building An Awesome Mobile Team
Hiring Tip: Graph Interview Performance Vs Years of Experience
Hiring Tips For Early Stage Startups: How to Get Your First 3 Employees
Our 10 Step Hiring Process