How does one compare one image to another to see if they are similar by a certain percentage, on the iPhone?

As a quick, simple algorithm, I’d suggest iterating through about 1% of the pixels in each image and either comparing them directly against each other or keeping a running average and then comparing the two average color values at the end.

You can look at this answer for an idea of how to determine the color of a pixel at a given position in an image. You may want to optimize it somewhat to better suit your use-case (repeatedly querying the same image), but it should provide a good starting point.

Then you can use an algorithm roughly like:

float numDifferences = 0.0f;
float totalCompares = width * height / 100.0f;
for (int yCoord = 0; yCoord < height; yCoord += 10) {
    for (int xCoord = 0; xCoord < width; xCoord += 10) {
        int img1RGB[] = [image1 getRGBForX:xCoord andY: yCoord];
        int img2RGB[] = [image2 getRGBForX:xCoord andY: yCoord];
        if (abs(img1RGB[0] - img2RGB[0]) > 25 || abs(img1RGB[1] - img2RGB[1]) > 25 || abs(img1RGB[2] - img2RGB[2]) > 25) {
            //one or more pixel components differs by 10% or more
            numDifferences++;
        }
    }
}

if (numDifferences / totalCompares <= 0.1f) {
    //images are at least 90% identical 90% of the time
}
else {
    //images are less than 90% identical 90% of the time
}