How do I detect that an iOS app is running on a jailbroken phone?

Checking if the kernel is broken isn't THAT much more involved.

Jailbreaking makes the kernel's signature check of signed code always report that code is signed correctly, unbroken phones cannot run code with a bad signature.

So, include a separate executable in the app with a bad signature. It could just be a 3-line program that has main() and a return value. Compile the executable without code signing (turn it off in Project Settings->Build) and sign it with a different key using the "codesign" commandline utility.

Have your app exec the separate executable. If your program can't get the return value when running the separate executable with the bad sig, it's definitely jailed. If the separate executable returns A-OK, the phone is definitely jailbroken.

It depends what you mean by jailbreak. In the simple case, you should be able to see if Cydia is installed and go by that - something like

NSString *filePath = @"/Applications/Cydia.app";
if ([[NSFileManager defaultManager] fileExistsAtPath:filePath])
{
   // do something useful
}

For hacked kernels, it's a little (lot) more involved.

This is a code that combine some answers I found for this need, and will give you much higher success rate :

BOOL isJailbroken()
{
#if !(TARGET_IPHONE_SIMULATOR)

   if ([[NSFileManager defaultManager] fileExistsAtPath:@"/Applications/Cydia.app"] ||
       [[NSFileManager defaultManager] fileExistsAtPath:@"/Library/MobileSubstrate/MobileSubstrate.dylib"] ||
       [[NSFileManager defaultManager] fileExistsAtPath:@"/bin/bash"] ||
       [[NSFileManager defaultManager] fileExistsAtPath:@"/usr/sbin/sshd"] ||
       [[NSFileManager defaultManager] fileExistsAtPath:@"/etc/apt"] ||
       [[NSFileManager defaultManager] fileExistsAtPath:@"/private/var/lib/apt/"] ||
       [[UIApplication sharedApplication] canOpenURL:[NSURL URLWithString:@"cydia://package/com.example.package"]])  {
         return YES;
   }

   FILE *f = NULL ;
   if ((f = fopen("/bin/bash", "r")) ||
      (f = fopen("/Applications/Cydia.app", "r")) ||
      (f = fopen("/Library/MobileSubstrate/MobileSubstrate.dylib", "r")) ||
      (f = fopen("/usr/sbin/sshd", "r")) ||
      (f = fopen("/etc/apt", "r")))  {
         fclose(f);
         return YES;
   }
   fclose(f);

   NSError *error;
   NSString *stringToBeWritten = @"This is a test.";
   [stringToBeWritten writeToFile:@"/private/jailbreak.txt" atomically:YES encoding:NSUTF8StringEncoding error:&error];
   [[NSFileManager defaultManager] removeItemAtPath:@"/private/jailbreak.txt" error:nil];
   if(error == nil)
   {
      return YES;
   }

#endif

   return NO;
}

+(BOOL)isJailbroken {
    NSURL* url = [NSURL URLWithString:@"cydia://package/com.example.package"];
    return [[UIApplication sharedApplication] canOpenURL:url];
}

Checking the file path /Applications/Cydia.app is not allowed on a normal phone? I've never heard of Apple detecting this and rejecting an app for it, but Apple is unpredictable. Cydia has a URL scheme cydia:// which can be legally checked with UIApplication canOpenURL: