Update (Sep 2013): Wow. 50.000 downloads in just 3 months! I did not expect this plugin to grow so popular this fast. There is now a Pro version containing some more advanced features: Mailchimp for WordPress Pro.
Around 2 years ago I started development of Newsletter Sign-Up, my most popular WordPress plugin which has been downloaded close to 150.000 times by now.
A lot of people using this plugin were using it with Mailchimp which is why I decided to develop a completely new plugin dedicated to just this newsletter service: Mailchimp for WordPress.
It does everything that Newsletter Sign-Up did, plus more. Because the plugin only supports Mailchimp I could add specific features and greatly simplify other parts of the code base. It utilizes the Mailchimp API so configuring the plugin got a lot easier as well. All you need is your Mailchimp API key and the plugin will fetch all of your list and other settings to ease configuring the rest of the plugin.
I tried to make the plugin as flexible as possible. You can build your own form HTML (yes, anything), but the plugin tries to give you a (big) hand by providing you with a field wizard which will generate the HTML for you.
Also, almost all plugin settings are optional. Install the plugin, enter your API key, use the form shortcode or form widget to add a sign-up form somewhere and off you go.
The plugin can be downloaded for free from the WordPress repository here.
Hope you like it, enjoy!