Rewriting nested for loops to give better formatted output
You should extract out at least two methods:

boolean isMatchingClients(final Client client, final Client otherClient) { ... }
int calculateCommonInterests(final String clientInterests, 
    final String otherClientInterests) { ... }


It would improve readabilily a lot and make the code more flatten.

I usually prefer final variables. Making a variable final relieves the programmer of excess mental juggling - he/she doesn't have to scan through the code to see if the variable has changed. (From @nerdytenor's answers.)
Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. 

For example, the count variable could be right before the second for loop:

int count = 0;
for (int c = 0; c &lt; numberOfClients; c++)


(Effective Java, Second Edition, Item 45: Minimize the scope of local variables)
If it's possible I'd consider storing the interest data in BitSets. Then it would be possible to and two of them and get the number of common bits with the cardinality method. Here is some test code:

@Test
public void testBitSet() {
    final BitSet interestBitSet = createBitSetFromString("11100111");
    final BitSet otherInterestBitSet = createBitSetFromString("11001001");

    final BitSet clone = (BitSet) interestBitSet.clone();
    clone.and(otherInterestBitSet);

    assertEquals(3, clone.cardinality());
}

private BitSet createBitSetFromString(final String input) {
    final BitSet result = new BitSet();

    final char[] inputArray = input.toCharArray();
    for (int index = 0; index &lt; inputArray.length; index++) {
        if (inputArray[index] == '1') {
            result.set(index);
        }
    }
    return result;
}


The and method modifies the bitset which is a disadvantage here. Cloning helps, although it's not the most beautiful solution.
Instead of 

System.out.println("");


you could use

System.out.println();

You could remove some duplication:

if (count == 0) {
    System.out.println(clientDetails[b].getClientName() + "is compatible with the following client(s)");
    System.out.println("\t" + clientDetails[c].getClientName());
} else {
    System.out.println("\t" + clientDetails[c].getClientName());
}


The following is the same:

if (count == 0) {
    System.out.println(clientDetails[b].getClientName() + "is compatible with the following client(s)");
}
System.out.println("\t" + clientDetails[c].getClientName());

I'd create local variables for clientDetails[b] and clientDetails[c]. They are used a lot.
About the output: if you want to show the number of compatible clients in the header you have to count them (and maybe store them in an ArrayList to avoid running the loop twice) before printing the header. If you are not allowed to use ArrayLists I don't think that it's worth it.
I don't know what's the type of the clientGender field. If it's String, you should not compare it with != or ==. See: Java String.equals versus ==
The anyMatch variable is duplicated, it could be eliminated. It only stores the state whether count == 0 or not.

final boolean anyMatch = (count &gt; 0);
if (anyMatch) { 
    ... 
}



Some optimization ideas:


Use two arrays: one for males, one for females, so you don't have to compare clients with the same sex.
Order the arrays by age and skip the definitely non-matching clients. You could use binary search here.
Use a two-dimensional array with the first dimension as the age. The second dimension contains the clients with the corresponding age.
You could use one array which is sorted by gender then age. You could use Arrays.sort and a custom compareTo method in the Client class:

@Override
public int compareTo(final Client o) {
    final int nameResult = name.compareTo(o.name);
    if (nameResult != 0) {
        return nameResult;
    }
    return age - o.age;
}



Finally, here is my two methods after the refactorings mentioned above:

public static void matchClients(final Client[] allClients) {
    for (final Client client: allClients) {
        checkClient(client, allClients);
    }
}

private static void checkClient(final Client client, final Client[] allClients) {
    int matchCount = 0;
    for (final Client otherClient: allClients) {
        if (!isMatchingClients(client, otherClient)) {
            continue;
        }
        if (matchCount == 0) {
            System.out.println(client.getClientName() + 
                "is compatible with the following client(s)");
        }
        System.out.println("\t" + otherClient.getClientName());
        matchCount++;
    }
    final boolean anyMatch = (matchCount &gt; 0);
    if (!anyMatch) {
        System.out.println(client.getClientName() + 
            "is not compatible with any client.");
    }
    System.out.println();
}