How do Promises/A+ implementations vary?

What aspects of a promise library does the spec not cover? What kind of things vary between implementations?

Please illustrate with examples of actual differences (eg between Bluebird and Q).

Almost everything. The Promises/A+ spec is aimed for promise interoperability, it's built so promise libraries (and now, native promises) can talk to each other. The idea is for it to be possible to predict how a promise behaves and to define how promises are assimilated by other libraries.

Quoting the specification:

This specification details the behavior of the then method, providing an interoperable base which all Promises/A+ conformant promise implementations can be depended on to provide. As such, the specification should be considered very stable. Although the Promises/A+ organization may occasionally revise this specification with minor backward-compatible changes to address newly-discovered corner cases, we will integrate large or backward-incompatible only after careful consideration, discussion, and testing. Finally, the core Promises/A+ specification does not deal with how to create, fulfill, or reject promises, choosing instead to focus on providing an interoperable then method. Future work in companion specifications may touch on these subjects.

The following are not covered:

Creating a promise (that's the promise constructor spec).
Promise aggregation (although most implementations support .all).
Progression (that's the progression spec, which will soon be replaced imo).
Cancellation (that's the cancellation spec).
Unhandled rejection monitoring (there is no spec, but there is an inspection discussion).
Stack traces.

Bluebird and Q for example, are both completely Promises/A+ complaint but differ on a lot of these:

The next Q, v2 introduces estimation, where Bluebird intends to deprecate progression eventually in favor of something like C#'s IProgress.
Creating a promise is usually done with deferreds in Q (although it now offers a promise constructor variant), Bluebird encourages the promise constructor.
Bluebird has more robust and stronger promisification abilities, turning a whole callback API to promises in a single command. Q author Kris built Q-IO which manually promisifies the filesystem and http modules.
Bluebird allows scoped binding of this value via .bind, and promise array methods (.map,.reduce,.filter etc).
Q has primitives like asynchronous queues, and RPC via Q-connection in mind,
Bluebird is about 100 times faster, has better stack traces, and automatic unhandled rejection detection. It also consumes a lot less RAM memory per promise.