Short answer:
It depends on your application - the AMI will always be the starting point, how much you need to customize your instance when it launches will determine what more you need beyond the simple 'autoscale instances behind a load-balancer' example.
Not so short answer:
Instances on EC2 are very much like VPSes - in fact, they are virtual machines (Amazon uses Xen virtualization). The key difference I see between a VPS and a 'Cloud' servers is the ease of deployment - provisioning and adding a dozen instances or a few hundred GB of storage in the 'cloud' should be a trivial task.
Since Amazon uses virtual machines, they have 'images' of those machines. These images reference the storage and contain a reference to a default kernel (which you can change). The contents of this image will typically be used to create the root volume that is attached to an instance.
You are largely stuck using the (fairly numerous) kernels that Amazon provides - compiling your own is usually not an option - but you can set most parameters and make use of the available kernel modules to achieve what you want. Once you have created your own AMI, all instances you launch from it will be the same (baring any scripts you have the AMI run to customize itself). Which makes this the starting point for almost all cases.
There are some definite perks to the 'virtual' nature of things. For instance, you can switch the root volume by simply stopping the instance, detaching the root volume, attaching a new volume, and starting the instance back up. Likewise, you can change the instance type, by stopping the instance, modifying the instance attributes, and starting the instance again.
When you launch an instance, you specify (among other things), the instance type (e.g. m1.large) and the AMI. This means your instance will start up with everything that was saved on that AMI - a preconfigured operating system, whatever software you installed, etc. Additionally, the AMI (or the ec2-run-instances command) can reference additional storage - either ephemeral or EBS backed. In the case of additional EBS storage volumes, these can be created from existing snapshots and attached to your instance when it starts. (Interestingly, the contents of these snapshots are loaded 'lazily' - meaning you can access the data on them, before the snapshot has fully loaded, advantageous if you are loading large volumes).
Consider the simplest scenario - a cluster where all machines are equivalent - to begin with, let's say we are serving a static site. EC2 will let you scale vertically (more powerful instance) and horizontally (more instances). So, we start with the smallest instance - a t1.micro, and we find that eventually, it can't handle the load. We could now add a second instance behind an Elastic Load Balancer (ELB). So, an incoming request would go to the ELB (which is supposed to be designed with redundancy and scalability in mind - it should automatically add more resources to meet the demands placed on it) - and it will route it to one of the instances, that instance will process the request and return it through the load balancer.
To automate the process a bit more, we could go with Amazon's autoscaling - essentially, using triggers (values of Cloudwatch metrics) you can add and remove instances on the fly (and just like launching an instance manually, you specify the instance type and AMI of the new instances). Moreover, those instances can be (they don't have to be) associated with an ELB automatically growing or shrinking your cluster based on the variations in some metric (e.g. CPU load, RAM usage, or some other custom variable).
Now - pretty much everything about the above scenario is 'bad practice' - you probably shouldn't scale horizontally from a t1.micro as they are rather underpowered instances - so you would first increase the instance size; the cost of an ELB is far more than that of a (reserved) t1.micro making it (economically) impractical in this scenario; and if you were serving a static site on AWS you'd just use S3 and forgo the expense and hassle of instances altogether, but the point is an illustration.
Let's take a more complex example - a PHP/MySQL site (e.g. Wordpress). Firstly, we separate the database from the web server - so let's start with one instance of each - we can now scale each independently. Arguably, instead of hosting MySQL ourselves, we could use Amazon's RDS (although, personally, I prefer to maintain my own MySQL setup) which would simplify the deployment of additional MySQL instances (... for a price, of course). Our web servers are all serving the same content, but now it is possible that the content may change. The changes (e.g. a new article, comment, etc.) that are stored in the database are not a problem - all servers are reading from the same database instance. Ideally you will store your code in some central location (e.g. S3) and each instance will pull it when it launches. Static assets can be served from a CDN, so that you can avoid dealing with a distributed filesystem locally. (The ELB can handle sticky sessions, but it is preferable to simply store you sessions centrally (e.g. Memcached) so that all instances have access to them - keep in mind that a request can end up on any instance).
(AWS does have Elastic Beanstalk - which is supposed to handle the provisioning of the resources needed by certain classes of application (e.g. PHP/MySQL) - but I have no personal experience with it).
For more complex setups, you can pass user-data to the instances, and there are methods to getting a list of all the instances you have running (and you can tag your instances to group them as you need). You can process tasks in message queues (the Amazon version being Simple Queue Service... or go with an open source version if you want) so that you ensure your cluster only processes each request once. Of course, you can also control your cluster using the typical high availability tools (e.g. Heartbeat/Corosync, Pacemaker, etc.) - which will let all the nodes be 'aware' of each other, and give you control over the resources running on each node. Add a distributed filesystem (e.g. Gluster) and you can handle most scenarios.
Beyond this, you can still use the same tools you mention. Most of the ideas above are based on having the same AMI deployed multiple times (you customize your AMI, and launch multiple copies of it - each of which should be equipped to handle its own basic configuration (e.g. pull the latest code, etc)). If your instances are either going to be changing often, or you have a larger cluster (e.g. where it would be problematic to roll out changes to all the nodes), or if your nodes are not similar - then you can deploy nodes with your choice of configuration management software (e.g. Puppet, Chef, etc).
There is yet another step you can go with - which is to provision your own 'Virtual Private Network' - essentially, allowing you to create some private facing and some public facing instanes with NAT, and control over the private IP address and the network interfaces (e.g. you can have multiple interfaces on a single instance).
In the end, how you deploy your application is very much dependant on the requirements of the application - what information each node needs to share, how many nodes there are in your cluster, and which nodes are dependant on each other. The easiest scenario will always be the one where each node can operate independently of each other, and a request going to any node will yield the same result... launch an instance, customize it, create your AMI, and autoscale it behind an ELB. All other scenarios will require a bit of planning to design something that will scale effectively.
Given the above, I feel it is important to point out the flip side - AWS is a great service - because there is a low barrier to entrance - you can learn it essentially for free (they do have a free tier) - and you it can scale with your needs. However, every last thing on AWS has a charge to it - the number of hours you run an instance, the number of GB you store, the amount of I/O on your disk, the number of requests you make to S3, the (outgoing) bandwidth you use - everything. It is easy for unforseen things to rack up quite a bill in a fairly short time-span. AWS is definitely not the solution to every problem and it is not without its limitations (e.g. no broadcast/multicast packets on their network).
(Well, this ended up being a bit more than the few lines I had intended to write...)
