Cards -> Add Field -> Dates.
Edit: This is in Address Book on OS X, I presume there's some thing similar in iOS...
Edit 2: When you edit a contact in iOS (4.3.4, at least) you can "add field" at the bottom. "Anniversary" is the default (as you figured out

).

Last edited: