Indeed, the maritime operations are undertaken by a coalition of nations that choose to participate and are not under the leadership of the alliance. That said, if you look at the nations that are involved, there are a few of the coastal states that participate. Pakistan, for example, recently had the leadership of one of the maritime interdiction zones in the region, but most of the navies are the highly capable western navies that are also NATO members.
On November 22nd, 2006. See this statement in context.