There is already the 'flag_thumb_as_new' plugin that does something similar:
http://www.zenphoto.org/2010/02/flag_thumb_as_new/

What is the best way to extend an existing plugin? I want to make it do the following:

• sets a cookie when I visit the gallery
• checks the last visited time
• adds a flag against images (and the images that contain them) that are new since the last visit

The fallback for non-cookie users would be the current date threshold option.

Well, take that plugin and extend it to your needs is the way...;-) This filter plugin is probably a good guide for what you want.