Larger gulls are not even fully mature until three or four years old (when they lose their last brown feathers), and they might not breed successfully for another year or two.
Presumably they can then live for a good few years more. That suggests that perhaps 10 years might not be unusual.
Smaller gulls are mature in their second or third year, so might live for a shorter time.
Having said all that, I've just done a Google search. This excellent page gives record recovery times for rung birds:
http://www.vogeltrekstation.nl/staav.htm
The gulls are the Larus and Rissa ones in the list, and all the common species are in the range 25 to 30 years (size doesn't seem to make much difference).
Remember that these are extreme records, and the average will be very much lower. However, some of the birds may have been rung when already adult, and may not yet be dead. Also, ringing has not been done on a large scale for all that many years, so some of these individuals may live for decades more.
I'd not realised quite how many different birds could be so long-lived -- and many of the shorter times are rarer birds for which there must be very few records. There's a fulmar and an oystercatcher there which were each 43!