I think I've manage to figure it out.
UILocalNotification *localNotification;
[localNotification setTimeZone:[NSTimeZone localTimeZone]];
[localNotification setFireDate:fireDate];
This will make whatever Date is in fireDate the time/Date that the notification will go off, in the user's current timezone. So it will go off at 6:00am in Sydney, then again at 6:00am in Los Angeles, etc.
So that part was working as intended, where I had made the mistake was in displaying the time.
Instead of the code in my question I needed to set the timeZone of the NSDateFormatter to the timeZone of the UILocalNotification:
UILocalNotification *myLN = <The UILocalNotification we've retrieved from somewhere>;
NSDateFormatter* df_local = [[[NSDateFormatter alloc] init] autorelease];
[df_local setTimeZone:myLN.timeZone];
[df_local setDateFormat:@"hh:mm"];
NSString* ts_local_string = [df_local stringFromDate:fd];