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 him or her 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 (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
This is to add to the other answers, which suggest looking for your followers in their default locations, like where you initially hired them, or their homes, following their default NPC schedules.
If you can't find them in their default locations, also look at the jails of the various cities or holds. An answer in Lydia goes to jail suggests that followers can be arrested and jailed. If arrested, they will make the jail their new "home."
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.