The code below calculates the first Tuesday of a given month/year combination. It's written in MacRuby because that is what I just tried it with, but you should have no problems to convert it to proper Objective-C, it's just a different syntax (I love MacRuby for quickly trying out an idea):
dc = NSDateComponents.alloc.init
# Set month to April 2010
dc.setYear 2010
dc.setMonth 4
dc.setWeekday 3 # 1 = Sunday, 2 = Monday, ...
dc.setWeekdayOrdinal 1 # We want the first weekday of the month
cal = NSCalendar.alloc.initWithCalendarIdentifier NSGregorianCalendar
date = cal.dateFromComponents dc
date.description # => "2010-04-06 00:00:00 +0200"
I leave it to you to determine the "next first Tuesday" from a given date: do the calculation for the month of the current date first and if the result is in the past, do it again for the following month. Use -[NSCalendar components:fromDate:]
to get the month/day combo of a given NSDate.