Previous to iOS 6, opening a URL like this would open the (Google) Maps app:
NSURL *url = [NSURL URLWithString:@"http://maps.google.com/?q=New+York"];
[[UIApplication sharedApplication] openURL:url];
Found the answer to my own question. Apple documents its maps URL format here. It looks like you can essentially replace
Update: It turns out that the same is true in MobileSafari on iOS 6; tapping a link to
http://maps.apple.com/?q=... opens the Maps app with that search, the same way
http://maps.google.com/?q=... did on previous versions. This works and is documented in the page linked above.
UPDATE: This answers my question relating to the URL format. But nevan king's answer here (see below) is an excellent summary of the actual Maps API.