As of January 30, 2013, Google will no longer allow new iPhones, iPod touches, iPads, or other devices to be setup using Google Sync (their implementation of Microsoft's excellent ActiveSync protocol). While existing Google Sync setups will keep working, the next time you want to add Gmail to a device, you'll have to use something else -- namely Google's eccentric IMAP service, which works with Apple's Mail app and allows for a unifed inbox with other, non-Gmail accounts, and the Gmail app, which is excellent but is a silo unto itself.
How to set up Gmail in Google's Gmail app
Google's Gmail app is outstanding, supporting both push email, multiple accounts, and all the unique Gmail features like stars and labels, of course. You even get easy access to vacation responders and other options. If you only use Gmail for your email, it's absolutely the best way to go. If you use multiple email providers, but don't mind accessing them via separate apps, it's also a great choice. Sadly, you can't set third party apps as default in iOS, so you'll probably need to set up your account in Apple's iOS Mail app as well, for convenience sake. (See below.)
Tap Open once Gmail finishes downloading, or if you've left the App Store, tap the Gmail icon on your Home screen.
Enter your Gmail or Google Apps email address and password.
Tap sign in.
How to setup Gmail in Apple's Mail app
Gmail is one of the main email setup options in Apple's built-in iOS Mail app. It uses IMAP to receive email, but due to Google's non-standard configuration, and Apple's lack of specific support for that non-standard configuration, you won't get push email, and you won't have access to stars, labels, and other Gmail-specific conventions. Sadly, it also doesn't automagically include contact sync, so you'll have to set that up separately.
You will, however, have your Gmail included in the unified inbox, which is incredibly convenient if you also have other, non-Google email accounts (like iCloud, Exchange, Hotmail, etc.)
Launch Settings from your Home screen.
Tap Mail, Contacts, Calendars.
Tap Add Account...
Enter your name, Gmail email address, password, and a descriptive name (like Gmail, or Personal, so you can identify it later).
Select which services you want to leave on for sync, Mail, Calendars, and Notes. (You probably want all of them on.)
How to setup Gmail Contact Sync with CardDAV
To set up contacts sync, repeat the same procedure, with a slight change in settings.
Tap Add Account... again.
Tap Other at the bottom.
Tap Add CardDAV Account
Enter google.com as the server.
Enter your Gmail/Google address as the user name.
Enter your Gmail/Google password as the password.
Enter a description. For example, Gmail Contacts or Google Contacts.
Tap Next at the top right.
That's it, your contacts will now sync along with everything else.
How to set up Gmail's 2-step verification
If you're a high value target and worried about your Gmail security, you can also setup and use Gmail 2-step verification on your iPhone, iPod touch, or iPad. For most people, it's probably more trouble than it's worth, but it's there for those who really need it.