When you get to Sanctuary, he gives you a quest where the reward is to access his stash. Once you complete it, you'll have a temporary option to hit a button (Q in the PC version) to give him a high five. He'll raise his hand.
At that point, hit your melee button (V in the PC version) to attack his hand. This will count as a high-five.
Be warned, though: if you're playing co-op and someone else completes the high-five, Claptrap doesn't allow you to request another one. :(
Edit, since this is the accepted answer: There is at least one other opportunity that has been identified by other answers on this question as times when Claptrap will ask for a high five. Here's the full list:
In all cases, the tactic is the same: When he holds up his hand, use your melee attack to hit it.
On a side note, once I'd given him the high five as part of "Wildlife Preservation", I could request one at any time.
Even if you don't give Claptrap the high five in "Wildlife Preservation", as long as you complete the mission you can request the high five at any time. Aim at his hand and press V