API GatewayにはCORSを有効にする設定があり、ボタンひとつで必要なヘッダー情報の付与などをしてくれる。
参考: http://docs.aws.amazon.com/ja_jp/apigateway/latest/developerguide/how-to-cors.html
が、自分の環境（ajaxでAPI Gatewayのエンドポイントを叩くようなWEBアプリを作っている）では上記設定を完了しても依然として No 'Access-Control-Allow-Origin' header is present on the requested resource. というエラーが出てしまっていた。
いろいろ調べた結果、以下のstackoverflowにたどり着いた。
http://stackoverflow.com/questions/34325009/aws-api-gateway-endpoint-gives-cors-error-when-post-from-static-site-on-s3
つまり、API Gatewayに対するアクセス自体が異常終了した場合は、設定されたヘッダー情報などは反映されずにレスポンスが帰ってくる様子。なので見直すべきはCORSの設定ではなく、APIを叩く側の形式であったり、API Gatewayのマッピングテーブルであった。
今回は、ajaxでjsonをputしていたのだが、その形式がおかしくて途中（詳しく見てないがおそらくパラメータのマッピング？）でAccess-Control-Allow-Originが設定されていないレスポンスが帰ってきてたようだった。