Linked just means they actively federate, allowed is a remnant from when the federation was strictly allow-list based in the early days (might be still possible to enable as a site admin), and blocked means exactly that.
The default is that any instance can federate, but only after a user actively requested that it is added to the list of linked instances. There is no central relay or so that tells an instance which other instances exists, so it needs to build up a list of known linked instances.
So if a user searches for a community on another instance, does that mean that the instance that they're following is automatically added to the linked list or no?
If so, does that happen when they subscribe or when they search?
As far as I know, yes. I am not 100% sure if searching but not interacting is sufficient. But I think a reply is sufficient, not only actual subscriptions.