When setting up Google’s 2-step authentication, you will also have to create application specific passwords for apps which are not ready to use this new process natively, e.g. Apple Mail.
Once you have created app-specific passwords, to make later identification easier you might want to name these based on the device and app, e.g. iMac Apple Mail, etc.
On the respective device you will be prompted to enter your new password, however also check under Apple Mail > Preferences > Accounts > Account Information that the proper password is used for both the Incoming and Outgoing Mail Servers.
At this stage you might think that you are done, but it really depends on how your Gmail (Apps) account was originally setup. If you happen to get an error message in Apple Mail that reads…
‘Unable to connect… The server returned the error: Application-specific password required: http://support.google.com/accounts/bin/answer.py?answer=185833 (Failure)’
…then open System Preferences > Mail, Contacts & Calendars > YOUR GMAIL ACCOUNT and provide your app specific password here as well, in fact you will be prompted as soon as you select YOUR GMAIL ACCOUNT.