I often hear "I'm going to catch up with him" or "I'm going to follow up with him" but I don't understand the difference.
'Catch up with', while it can literally be a physical meeting, is informally used here to generally mean 'get or exchange news'. Friends who are meeting after a period of separation might catch up with each other. It may be used in more formal settings, like work, but is still usually seen as a less formal way of speaking.
'Follow up with', which is not used literally, is a more formal way of saying 'getting, giving or exchanging information' with another party. It's more often used in regards to business that one party has with another. In the US, a person is unlikely to 'follow up with' anything that's personal in regards to friend or acquaintance.
To catch up is to match someone in some measure of progress.
“Oh, you're watching Awesome Series too? Which season? I'd love to chat about it with you, but I don't want to risk spoilers, so I'll wait a bit for you to catch up to me.”
In the social sense, it means to share recent news, so that neither is “behind” in knowledge of the other's status.
“I haven't seen you in years! We have so much to catch up on!”
To follow up on an action is to take the next step in a process initiated by the previous action. To follow up with someone usually means to have a conversation about their progress on a project and what to do next.