What does it mean for a function to return an interface?

Think about this way: If Cat where a regular class, what exactly would you care about when you wanted to call some methods on it?

You'd care about the method definitions: their names, their argument types, their return values. You don't need to care about the actual implementation!

Since an interface provides all of that, you can call methods on it, just as you can on a regular class.

Of course, in order for the method to actually return some object, there needs to be some class that implements that interface somewhere. But what class that actually is or how it implements those methods doesn't really matter to the code that gets that object returned.

In other words, you can write code like this:

Cat cat = nextCat(GameState.STUFF);
cat.makeCat(GameState.OTHER_STUFF);

That code has no knowledge of the concrete type that implements the Cat interface, but it knows that the object can do everything that the Cat interface requires.

This function returns an object of a class which implements the Cat interface. The implementation details (for this concrete class) are up to you, as long as you implement all the methods of the Cat interface for it.

For example you could do this:

interface Cat {
    String meeeeow();
}

public Cat nextCat(GameState state) {
    return new Cat() {
        public String meeeeow() {
            return "meeeeeeeeeow!!!!";
        }
    };
}

in which case the method nextCat returns an implementation of the Cat interface by means of an 'anonymous-inner-class'. This shows that the code calling nextCat does not need to know which code implements the returned Cat interface. This is an example of one of the key strengths of Object-Oriented programming: because the calling code doesn't know the implementation, the impact of changing the implementation later on is small (as long as the interface remains the same).