There are much more in-depth discussions on the matter, but in a nutshell, you only need to release anything that you "own". You generally own any *objects* that you send a message that contains "alloc" or "copy".
Objects created with convenience constructors are auto-released. Generally at the end of the current method.
Code:
// you own this one, need to release
NSString *myString = [[NSString alloc] initWithFormat:@"Hello %@", @"world"];
// convenience constructor, will be auto-released
NSString *myString = [NSString stringWithFormat:@"Hello %@", @"world"];