Audiences is one of many services reliant on the Marketing Cloud ID service. That means in order for things to work properly, the ID service has to be implemented.
If you're using Dynamic Tag Management, this process is as simple as adding the ID service tool. Just make sure your solution libraries (particularly for Analytics and Target) are up to date.
More info on the ID service tool available here.
If you are using another tag managment system or deploying directly to the page, use the instructions found here instead.