Guys, you can remove the ads by going to your
Manage Your Kindle page, clicking on Manage Your Devices on the left column and you should be able to see your Kindle listed.
One of the columns shown is Special Offers and it should show you are "Subscribed" and next to that would be a link that says "Edit".
Click that and you'll be able to unsubscribe to the Special Offers and no longer get any ads. You'll have to pay US$40 to unsubscribe for the Touch. I don't how much it is for the Kindle 3. The basic Kindle 4 is $30, iirc. You'll also need a valid US address, if you haven't already.
EDIT: Beaten by tubemonkey!