Here is a good article from the MDC which explains the problems (and solutions) to form autocompletion.
Microsoft has published something similar here, as well.
To be honest, if this is something important to your users, 'breaking' standards in this way seems appropriate. For example, Amazon uses the 'autocomplete' attribute quite a bit, and it seems to work well.
If you want to remove the warning entirely, you can use JavaScript to apply the attribute to browsers that support it (IE and Firefox are the important browsers) using someForm.setAttribute( "autocomplete", "off" ); someFormElm.setAttribute( "autocomplete", "off" );
Finally, if your site is using HTTPS, IE automatically turns off autocompletion (as do some other browsers, as far as I know).
Update
As this answer still gets quite a few upvotes, I just wanted to point out that in HTML5, you can use the 'autocomplete' attribute on your form element. See the documentation on W3C for it.