Is the Promise constructor callback executed asynchronously?

It depends on the implementation of the promise. If we check the spec. You can find the final spec here - since this answer was originally written, it has been finalized.

Here is the relevant excerpt (you can find the original source here)

10. Let completion be Call(executor, undefined, «resolvingFunctions.[[Resolve]], resolvingFunctions.[[Reject]]»).
11. If completion is an abrupt completion, then
    • Let status be Call(resolvingFunctions.[[Reject]], undefined, «completion.[[value]]»).
    • ReturnIfAbrupt(status).

The ES6 standard indicates that the fulfillment of a promise is always asynchronous (See section 25.4.5.3, Promise.prototype.then and accompanying section 25.4.5.3.1, PerformPromiseThen). I have placed the relevant material below.

PerformPromiseThen

8. Else if the value of promise's [[PromiseState]] internal slot is "fulfilled",
   • Let value be the value of promise's [[PromiseResult]] internal slot.
   • Perform EnqueueJob("PromiseJobs", PromiseReactionJob, «fulfillReaction, value»).
9. Else if the value of promise's [[PromiseState]] internal slot is "rejected",
   • Let reason be the value of promise's [[PromiseResult]] internal slot.
   • Perform EnqueueJob("PromiseJobs", PromiseReactionJob, «rejectReaction, reason»).

TLDR: the function passed to the promise is executed synchronously, but subsequent then calls are always executed asynchronously.

The other answer proves this, but let me talk about the reasoning:

Promise constructor

The promise constructor callback (as specified either in the ES6 spec or the constructor spec libraries implement) will always be executed synchronously - this is in order to extract a deferred (older form of promise construction) out of it in case you need to have access to the resolve callback:

var r;
var p new Promise(function(resolve, reject){
    r = resolve;
});
// use r here, for example
arr.push(r);

then callbacks

then will always be executed asynchronously, virtually all mainstream promise implementations (Native, bluebird, $q, Q, when, rsvp, promise, jQuery (as of 3.0) etc) as well as native promises implement (or implement a superset of, with more constraints) Promises/A+.

This is exactly the reason that Promises/A+ was created out of Promises/A. Asynchronous guarantees will be preserved and Zalgo won't be released. (Also see this post).

The fact this happens (asynchronous guarantee) is completely intentional and actively prevents race conditions. Code in- and outside of then will always execute in the same order.

Here is the relevant quote:

onFulfilled or onRejected must not be called until the execution context stack contains only platform code. [3.1].