Typically the same way you deal with all of the other new resources / abilities that you gain on level-up (e.g. Wizard spells, new feats, etc.).
The most common way is to restrict leveling up to some kind of downtime. When the game resumes, the new spells have been learned, the new techniques mastered, and the followers have been attracted.
It all just happens "off-screen," because training and meeting montages get old pretty quickly.
This has the advantage of satisfying both the narrative and the mechanics reasonably well. The NPC cohort is "explained," and at the same time players aren't playing without one of their feats.
I have occasionally seen groups put off the acquisition of a cohort until the next time the party reached town (these groups typically allowed leveling up mid-dungeon). This works fine, as long as the delay is small (not more than a session or so).
If it's going to be a while before an opportunity for the cohort to be introduced shows up, I would recommend either the "poof" method (uh, he's always been here) or banning the feat until it's more convenient.
I have seen followers put off longer than that (trickling in over time), as they generally have less of an impact on the game. I have also seen some DMs have followers begin to show up beforethe PC took the feat, for the sake of making the narrative a bit smoother.
Roleplaying Cohort Acquisition
I would recommend against fully roleplaying the acquisition of the cohort in most instances. A few paragraphs of "this is how you met" combined with a character whose background explains why he's looking for a cohort is generally sufficient.
There are several problems with fully roleplaying it out.
It creates a spotlight issue. This is an encounter that only one player really cares about. Everyone else is just kind of along for the ride.
It undermines the feat. If you're going to the trouble of fully roleplaying the recruitment process, what purpose is the feat serving?
Things get weird in the failure state. What happens if the player fails to reasonably attract their follower? Sticks their foot in their mouth, doesn't rescue them from the big-bad, etc.?
Do they lose the feat? Is the feat suspended until they can try again? And if so, how long until that happens?
The general rule of not rolling the dice unless you're okay with failure applies here.
So, who controls the cohort? On the one hand, the cohort is a semi-independent NPC, which falls under the DM's responsibility. On the other hand, the cohort is part of a PC's character concept, and should prioritize support of that concept over any plans of the campaign setting / DM.
As a practical matter, shared custody with the player taking the bulk of the responsibility is generally best.
During combat, there's little reason not to give control of the cohort to the player running it. Yes, this means that particular player will get more time as the active player. But that time will be spent regardless of who controls the cohort, and the DM already has a lot on their plate during combat.
The DM should mostly step in when the cohort's behavior is important for narrative purposes, or if the player is making the cohort do things that are a little too self-sacrificing (giving up gear, throwing themselves in front of monsters without support, etc.).
During narrative portions of the game, either the player or the DM can control the cohort (whichever makes sense at the time), with any conflicts defaulting to the DM.