If you don't need to support anything before 10.10 or iOS 8, you can use NSURLQueryItem with NSURLComponents.
If you need to support older versions of OS X or iOS, then the definitive answer can be found in URL Session Programming Guide:
CFStringRef encodedString = CFURLCreateStringByAddingPercentEscapes(
kCFAllocatorDefault,
originalString,
NULL,
CFSTR(":/?#[]@!$&'()*+,;="),
kCFStringEncodingUTF8);
with appropriate __bridge and __bridge_transfer casts, as needed.
The problem with your earlier approach is that the older NSURL APIs were designed... well, not to put too fine a point on it, wrong. The APIs assumed that you would want to encode an entire query string or even an entire URL at once, so they leave ampersands and other similar reserved characters alone. This is, of course, not typically what you would really want to do in practice, but it is the way that the original NSURL APIs all behaved.
As an added note, if you are trying to stick the result into, for example, an HTML attribute, you need to do the above, and then encode it a second time using an HTML entity encoding method. See Question 1105169 for help with that second step.