I believe Mastodon servers (and presumably, most of the rest) have a bootstrap list of other instances which they automatically federate with. If a user attempts to interact with an instance unknown to the server it then reaches out and begins federation. The user can follow, reply to and read the content on that server immediately, although sometimes it can take a little time for a full list of posts and profile data to appear. Admins can also choose various levels of blocking against federation of instances of their choice.
As a user this is all transparent. I follow loads of people from all over the Fedi (some of them not even microblogging platforms) and it basically just works.