How to do it...

1. Start with the usual CloudFormation template version and description:

      AWSTemplateFormatVersion: "2010-09-09" 
      Description: Create NAT Gateway and associated route.

2. The template must take the following required parameters:

      Parameters: 
        PublicSubnetId: 
          Description: Public Subnet ID to add the NAT Gateway to 
          Type: AWS::EC2::Subnet::Id 
        RouteTableId: 
          Description: The private subnet route table to add the NAT
            Gateway route to 
          Type: String

3. In the Resources section, define an Elastic IP that will be assigned to the NAT gateway:

      Resources: 
        EIP: 
          Type: AWS::EC2::EIP 
          Properties: 
            Domain: vpc

4. Create the NAT gateway resource, assigning it the EIP you just defined in the public subnet:

        NatGateway: 
          Type: AWS::EC2::NatGateway 
          Properties: 
            AllocationId: !GetAtt EIP.AllocationId 
            SubnetId: !Ref PublicSubnetId

5. Finally, define the route to the NAT gateway and associate it with the private subnet's route table:

      Route: 
        Type: AWS::EC2::Route 
        Properties: 
          RouteTableId: !Ref RouteTableId 
          DestinationCidrBlock: 0.0.0.0/0 
          NatGatewayId: !Ref NatGateway