今回は上記の図の中に、オレンジ色の枠線に囲まれている部分の設定方法を紹介したいと思います。
CircleCIからHerokuにデプロイする作業が非常に楽で、「PROJECT SETTINGS」の「Heroku Deployment」に従ってやれば基本的に問題ありませんが、AWS CodeDeployの場合、かなり面倒いです。

S3側

リビジョンを保存するバケットを確保します

出来れば新しいバケットを作った方が楽ですね。
ロケーション(Location)は「s3://<バケット名>/」ですので、
仮にバケット名をdummyにすれば、「s3://dummy/」になります。

IAM(Identity and Access Management)側

CodeDeploy用のIAMロールを作ります

CodeDeployが出来ることは、S3上のリビジョンを特定の条件（某タグがある）を満たす全てのEC2インスタンスに保存する作業です。CodeDeploy用のロール管理ポリシーはアマゾンさんが既に用意してあります。AWSCodeDeployRoleというものです。もし更なるセキュリティを配慮したければ、ポリシー内のResourceを弄ればいいと思います（CodeDeployのロールは外から触れないので、省略します）。今回のロール名を「CodeDeploy_DummyApplication」とします。念のため、デフォルトのポリシー名を貼付します。

AWSCodeDeployRole

{
  "Version": "2012-10-17",
  "Statement": [
    {
      "Effect": "Allow",
      "Action": [
        "autoscaling:CompleteLifecycleAction",
        "autoscaling:DeleteLifecycleHook",
        "autoscaling:DescribeAutoScalingGroups",
        "autoscaling:DescribeLifecycleHooks",
        "autoscaling:PutLifecycleHook",
        "autoscaling:RecordLifecycleActionHeartbeat",
        "ec2:DescribeInstances",
        "ec2:DescribeInstanceStatus",
        "tag:GetTags",
        "tag:GetResources",
        "sns:Publish"
      ],
      "Resource": "*"
    }
  ]
}

ロールを作成したら、信頼関係のIDプロバイダーに「codedeploy.amazonaws.com」がちゃんと入っているかどうかを確認した方がいいです。

EC2用のIAMロールを作ります

IAMロール２つを作成する必要があります。
次はEC2用のIAMロールです。このロールの役割はEC2ユーザーにS3上のファイルをアクセス権限を与えることです。
こちらのロールに適用するポリシーは先に自作する必要があります（全リソースにアクセスさせても気にしなければ、既に用意してくれたAmazonEC2RoleforAWSCodeDeployの使っても構いません）。
管理ポリシーの名前を「CodeDeploy-CHO-EC2-Permissions」と付けます。

CodeDeploy-CHO-EC2-Permissions

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Action": [
                "s3:Get*",
                "s3:List*"
            ],
            "Resource": [
                "arn:aws:s3:::dummy/*"
            ]
        }
    ]
}

ポリシーを作成できたら、ロールを作成します。「CodeDeploy-CHO-EC2」と呼び、先ほどの「CodeDeploy-CHO-EC2-Permissions」をポリシーとして設定し、信頼関係のIDプロバイダーにEC2を追加します。アクセスコントロールポリシードキュメントはこんな感じになるはずと思います。

アクセスコントロールポリシードキュメント

{
  "Version": "2012-10-17",
  "Statement": [
    {
      "Effect": "Allow",
      "Principal": {
        "Service": "ec2.amazonaws.com"
      },
      "Action": "sts:AssumeRole"
    }
  ]
}

CircleCI専用のユーザを作ります

IAMでCircleCI専用のユーザ（アカウント）を作った方が安全ですね。
CodeDeployのリビジョン作成で使用されるため、このユーザーのcredentialsは必ずダウンロードしてください。
このアカウントに必要になる権限はS3へファイルを置く権限及びCodeDeploy用のリビジョンを作成・デプロイを発火させる権限です。
今回はユーザーのインラインポリシーの中で、２つのユーザーポリシーを作成します。それぞれを「CircleCI-deployment-CodeDeploy-IAM-policy」（この中のResourceに出たIDはCodeDeploy用IAMロール「CodeDeploy_DummyApplication」のARNで見つかる）と「CircleCI-deployment-S3-IAM-policy」という名前にします。
以下ポリシーデータのサンプルです。

CircleCI-deployment-CodeDeploy-IAM-policy

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "Stmt14XXXXXXXX000",
            "Effect": "Allow",
            "Action": [
                "codedeploy:CreateDeployment",
                "codedeploy:GetApplicationRevision",
                "codedeploy:GetDeployment",
                "codedeploy:GetDeploymentConfig",
                "codedeploy:RegisterApplicationRevision"
            ],
            "Resource": [
                "arn:aws:codedeploy:ap-northeast-1:3XXXXXXXXXX1:*"
            ]
        }
    ]
}

CircleCI-deployment-S3-IAM-policy

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "Stmt1XXXXXXXXX000",
            "Effect": "Allow",
            "Action": [
                "s3:PutObject"
            ],
            "Resource": [
                "arn:aws:s3:::dummy/*"
            ]
        }
    ]
}

CodeDeploy側

新しいアプリケーションを作成します

今回のアプリケーション名を「DummyApplication」にし、デプロイグループ名を「CircleCI-Deploy-Group」にします。タグに合致したインスタンスが全部デプロイ対象になりますので、特別なタグを使用したいですね。今回は種類に「Amazon EC2」、キーに「CodeDeploy」、値に「CircleCI」を入れます。
デプロイ設定は状況次第です。今回は一番良く使われていそうな「CodeDeployDefault.OneAtATime」を利用します。トリガーあたりは今回の内容から外れている為、割愛します。サービスロールはIAMで作った「CodeDeploy_DummyApplication」を利用します。

ローカルファイル側

デプロイ先のフォルダを指定

CodeDeployに「どのファイルをどのフォルダに置くか」を教えなければいけません。その内容はcircle.ymlと同じところにあるappspec.ymlで記録されます。以下記入例：

appspec.yml

version: 0.0
os: linux
files:
  #ソースの場合（Javaウェブアプリケーションならwarファイルの場所を指定）
  - source: ./target/dummy.war
  #デプロイ先の場所（Tomcatサーバーを使っていたらwebappsの場所）
    destination: /opt/tomcat8/webapps/

EC2側

デプロイ先を作成します

EC2のインスタンス作成と起動に関しては省略させてください。注意点は以下の４つです。
1. インスタンスはAmazon EC2キーペアを使って作成すること。
2. IAMロールが付与されていること。（先ほどの「CodeDeploy-CHO-EC2」です）
3. インスタンスにタグを付けること。（先ほどの「CodeDeploy」と「CircleCI」です）
4. AWS CodeDeploy Agentがインスタンス内にインストールされていること。（インストール方法）

特に１と２を間違えてしまったら、再作成をせざるを得ない羽目になるはずです。
(特に２について、苦情がかなりあるみたいですが・・・)

CircleCI側

IAM(Identity and Access Management)ユーザを保存します

CircleCIのプロジェクトのセッティング（プロジェクト右にある歯車アイコンをクリック）に入ると、下のほうに「AWS CodeDeploy」という項目があるはずです。先ほど作った専用ユーザーの「Access Key ID」と「Secret Access Key」を入れて保存します。

circle.ymlを変更します

circle.ymlに全ての設定内容を書くため、Step2(application-wide settings)を無視します。circle.ymlにデプロイメント項目を追加します。例をご覧ください。

circle.yml

deployment:
    #ここは「staging」と「production」に設定できます。つまり実験環境と本番環境を分けてデプロイできます。
    staging:
        #どのブランチ（Github上のリポの）をデプロイしますか
        branch: master
        #CircleCIにデプロイ用のサービス名を教えます。（CodeDeploy以外に、HerokuやDockerもサポートされています）
        codedeploy:
            #アプリ名（CodeDeployで新しいアプリケーションを作成したときに、「DummyApplication」にしましたよね）
            DummyApplication:
                #デプロイしたいフォルダを指定します
                application_root: /
                #リビジョンに関する設定
                revision_location:
                    #リビジョンのタイプはS3です。リビジョンはS3に保存されるからです。
                    #ちなみに、CodeDeployのリビジョンはS3以外に、Githubをサポートしています。
                    revision_type: S3
                    #S3の設定です
                    s3_location:
                        #S3のバケット名です
                        bucket: dummy
                        #CircleCIが作ったリビジョンはどんなファイル名でS3に保存されたいかを指定します。
                        key_pattern: dummy-{BRANCH}-{SHORT_COMMIT}
                #今回のリージョンは東京です（間違えないように）
                region: ap-northeast-1
                #先ほどCodeDeployで作ったdeployment_groupです
                deployment_group: CircleCI-Deploy-Group
                #同じく、先ほど指定したdeployment_configです
                deployment_config: CodeDeployDefault.AllAtOnce

これで連携作業が一旦終了です。

CircleCIとCodeDeployの連携による開発自動化の実践

S3側