What is the difference between Amazon Linux and RedHat Enterprise Linux on AWS EC2?

Red Hat pricing details are here http://aws.amazon.com/rhel/ and Amazon Linux is here: http://aws.amazon.com/amazon-linux-ami/; as you say, RHEL implies additional cost, whilst Amazon Linux involves 'no additional charge' beyond the charges for running instances and related services.

Amazon Linux, like CentOS, is based on RHEL -- it is fundamentally a minimal/basic install of Red Hat Enterprise Linux (hence optimised for the purpose). Amazon are currently offering a year's free Amazon EC2 Micro Instance for new customers within the 'free usage tier', as per http://wpmu.org/would-you-like-a-free-server-for-a-year/. If you would like to try EC2 for free, because of the limited memory/resource availability for the 'Micro Instance', trying Amazon Linux makes sense.

Usually, the price you pay for the "Enterprise" versions (RHEL, SLES) isn't for a bonus in performance, but for a bonus in service. For example, a certain to-remain-unnamed provider of "enterprise" databases won't offer you any support unless you are running the database on a certified Linux (i.e., SLES, RHEL). If you don't have support contracts to worry about, there's little to be had in the "enterprise" distributions that is worth the price.

IMVHO.