NSSet and NSMutableSet are unordered collections, so you should probably choose some other data structure if you need to store items in order - like NSMutableArray.
The method removeLastObject will give you the last object that was added at the end of the array. If you want the "oldest" item in an array, you probably want to do something like this:
Code:
id oldest = [myMutableArray objectAtIndex:0];
[muMutableArray removeObjectAtIndex:0];
Remember to retain "oldest" if you need it to stick around - it might get dealloc'd when the array releases it.