Some things include documentation, speed to hello world, RESTfulness, simple authentication, aligned incentives, helpful examples, and customer service. What do you think?
Your documentation should be language agnostic. Everything should be described in regards to HTTP methods, not some aspect of your language, your language's standard library, or, god forbid, some third-party library in your language.
If you DO expect users to rely on a reference implementation, it should be as generic as possible. I'm not a [insert language here] programmer and I don't want to have to learn the ins and outs of [your sandboxing tool] and [your library management tool] and [some fistfull of random third-party libraries] in order to install and run your samples.
Always respond with the requested format, even on errors. Yes, I am advocating that you put a diaper (i.e. a try ... catch block that catches all errors) on your API endpoint. Diapers are generally a bad idea, but if I send you a json request that, for whatever reason, throws a server-side error, please return the error information in a json-parsable manner. django-piston is guilty of not returning json-parsable error pages, and it has the second-most followers of all bitbucker repositories. https://bitbucket.org/jespern/django-piston/wiki/Home
If possible, write sample clients on a variety of popular languages. Put your client on PyPi or RubyGems or npm or Pear or CPAN or whatever, just don't half-ass it.
Know your audience. It's perfectly possible that your target audience doesn't actually give a shit about RESTfulness and they're perfectly happy using SOAP or (gasp!) XML-RPC. Those things may not be "cool" in the buzzwordy world of dynamic scripting languages, but the reality is that they're still standards and yes, people do use them.
Be mindful of how insular HN is and where its interests lie; the HN userbase is representative of the HN userbase, not software developers as a whole. There's a creaking leviathan in the world of "enterprise" software whose foundation lies in things like Java and .NET and where mechanisms like SOAP and XML-RPC are still in use. SOAP is neither useless nor mandatory; it is used by a subset of the software development community, some of whom may be more than willing to give you good money to integrate with their services, if only you'd let them.
1) Reliability - it can be counted on to do its job.
2) Consistency - it does it in the same, or at least the same small set of, ways each time.
3) Clarity and Discoverability - it is easy to see or find out what it does.
In that same vein the documentation should be clear and to the point. See Amazon Flexible Payments as an example of what NOT to do. Ambiguous docs with tons of circular linking etc. made me want to kill myself and did end up killing my project. Just my .02.
Facebook, Stripe, and WePay have done this. It makes integration much easier when you can test API calls before writing any code.
I can suffer through any problem with a remote API so long as the documentation is clear, thorough and contains relevant examples. Stripe's API documentation is about the best I've seen in recent years.
They get bonus points for making the 'cut and paste' examples actually cut and pastable, as they don't have instances of "stripe.com/method/<your_api_key_here>", and instead of have "stripe.com/method/my_actual_api_key", which is super convenient.
Perhaps the only thing that good documentation can't trump is unreliability. This includes (obviously) an API that doesn't always return the right values, or that sometime's fails, but also includes rapidly changing API protocols.
Take the time to think about your APIs early, and try very hard to keep them from changing once they're established. Nobody wants to have to refactor their code because you refactored yours.