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

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.