Console commands (PC)
If you're playing on the PC, try teleporting your follower to your location through console commands. This is easier and faster (no loading screens) than going to your follower's location and getting them to follow you again.
Console commands to teleport your follower to the player's current location:
prid targets an entity - your follower in this case. Search for your follower's RefID at the UESP wiki's "Followers" article.
(Another method to target instead of using
prid <refID> is to open up the console and then click on an entity. This will automatically do
prid <RefID> for the clicked entity. However, this method won't be useful in your situation as the follower is not near your vicinity, and can't be clicked on.)
moveto player moves the targeted entity near the vicinity of the player.
Your follower should now be near you after doing this. If for some weird reason, they are dead (which happens sometimes), use the console command
resurrect 1. Your follower should go back to life.
If for another weird reason, your follower is still not near your vicinity after doing this, they may have been "disabled" from the game (might happen with NPCs that are long dead), making them not appear in the game. Type
enable in the console to remedy this. If your follower still isn't up, type
resurrect 1 again.
More info on console commands at the UESP wiki's "Console" article.
Platforms that do not support console commands
Look for your followers in their default locations, like where you initially hired them, or their homes, following their default NPC schedules. See their respective articles in the UESP wiki for info on their locations and schedules.
With the Hearthfire DLC, if you've made your follower the personal steward of one of your houses, then look for your follower at that house.
If you've recruited your follower to join the Blades, then look for them at Sky Haven Temple.
If you can't find them in their default locations, check the jails of the various cities or holds. An answer in the post, Lydia goes to jail suggests that followers can be arrested and jailed. If arrested, they will make the jail their new "home."
If married or recruited for the Blades, he will attempt to return to Darkwater Crossing every day, thus making him very hard to get hold of, since all purchasable homes and Sky Haven Temple are quite a long distance away from Darkwater Crossing. This bug is fixed by version 1.1 of the Unofficial Skyrim Patch.
Source: "Derkeethus", UESP Wiki
If you hire her and enter Jorrvaskr, she may disappear. If this
happens, check the Dragonsreach Dungeon.
Sometimes Jenassa may disappear from the Drunken Huntsman and will
instead be found standing stationary a short way off the main road
just west of Broken Fang Cave. Hiring her as a follower then
dismissing her will cause her to walk back to her normal location at
the Drunken Huntsman.
Source: "Jenassa", UESP Wiki
If she is not following you, she resides in the main hall of Dragonsreach, although if you purchase Breezehome, she will move there.
Source: "Lydia", UESP Wiki