Best way to remove from NSMutableArray while iterating?

This is a very simple problem. You just iterate backwards:

for (NSInteger i = array.count - 1; i >= 0; i--) {
   ElementType* element = array[i];
   if ([element shouldBeRemoved]) {
       [array removeObjectAtIndex:i];
   }
}

This is a very common pattern.

One more variation. So you get readability and good performace:

NSMutableIndexSet *discardedItems = [NSMutableIndexSet indexSet];
SomeObjectClass *item;
NSUInteger index = 0;

for (item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addIndex:index];
    index++;
}

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];

Some of the other answers would have poor performance on very large arrays, because methods like removeObject: and removeObjectsInArray: involve doing a linear search of the receiver, which is a waste because you already know where the object is. Also, any call to removeObjectAtIndex: will have to copy values from the index to the end of the array up by one slot at a time.

More efficient would be the following:

NSMutableArray *array = ...
NSMutableArray *itemsToKeep = [NSMutableArray arrayWithCapacity:[array count]];
for (id object in array) {
    if (! shouldRemove(object)) {
        [itemsToKeep addObject:object];
    }
}
[array setArray:itemsToKeep];

Because we set the capacity of itemsToKeep, we don't waste any time copying values during a resize. We don't modify the array in place, so we are free to use Fast Enumeration. Using setArray: to replace the contents of array with itemsToKeep will be efficient. Depending on your code, you could even replace the last line with:

[array release];
array = [itemsToKeep retain];

So there isn't even a need to copy values, only swap a pointer.

For clarity I like to make an initial loop where I collect the items to delete. Then I delete them. Here's a sample using Objective-C 2.0 syntax:

NSMutableArray *discardedItems = [NSMutableArray array];

for (SomeObjectClass *item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addObject:item];
}

[originalArrayOfItems removeObjectsInArray:discardedItems];

Then there is no question about whether indices are being updated correctly, or other little bookkeeping details.

Edited to add:

It's been noted in other answers that the inverse formulation should be faster. i.e. If you iterate through the array and compose a new array of objects to keep, instead of objects to discard. That may be true (although what about the memory and processing cost of allocating a new array, and discarding the old one?) but even if it's faster it may not be as big a deal as it would be for a naive implementation, because NSArrays do not behave like "normal" arrays. They talk the talk but they walk a different walk. See a good analysis here:

The inverse formulation may be faster, but I've never needed to care whether it is, because the above formulation has always been fast enough for my needs.

For me the take-home message is to use whatever formulation is clearest to you. Optimize only if necessary. I personally find the above formulation clearest, which is why I use it. But if the inverse formulation is clearer to you, go for it.