One of my favorite character types to use as a GM is the Nemesis. It is also one of my favorite things to run into as a player as well. Now, I've talked about something similar here before with this post about good villains, but when you come down to it a nemesis is something much more than just a villain. In fact, a nemesis doesn't even have to be a villain for the game and can still exist. Granted, your players probably won't see it this way since a nemesis is an enemy, even if not a villain. So, what makes a good nemesis? Well, I'll tell you my theory on it.
The Long Game
One of the best parts about the nemesis in my opinion is that they are part of the long game. A short lived nemesis isn't very entertaining, and in my opinion isn't even a nemesis. Know, their needs to be history and development between the two. None of this one and done stuff that so many PCs seem to go for. A long lasting relationship is better, and preferably one where the nemesis wins on occasion. It makes it more personal for the PC, and keeps the nemesis being treated with respect. You don't want it to be "oh, here comes that guy again. Haven't I beat him like a bajillion times already?" You want someone who has left a mark on the player, made them feel like they were defeated. Someone who has put a couple of notches up on their side of the score card, and thus demands to be treated with respect. That is what gets you a good nemesis.
A Reflection of the Hero
A long with the history, the nemesis needs to resonate with the hero. This is done in one of two ways usually. The first is to make the nemesis the opposite of the hero. If the hero is super strong and invulnerable, the kind to always take the direct path; then the nemesis is super smart, the kind that always takes a myriad of angles in their attacks. Strangely, this relation rarely works in the opposite, with the super strong nemesis and the super smart 'hero', though I suppose it could. Instead though, the super smart hero is usually confronted with the other kind of nemesis, the mirror reflection.
What do I mean by mirror reflection? Well, basically I mean that the nemesis is very similar to the PC, but something is different. Perhaps their methods are just a bit more extreme, or they do things just a bit differently. Either way, the similarities are there, even if just beneath the surface, and as the player comes into contact with their nemesis again and again, the thought should come up wondering at how different exactly they are from each other.
For examples you need look no further than the classics. For opposites, you have Superman and Lex Luthor. Superman the direct hero, whose response to most things is to punch it. Lex Luthor, the genius villain who schemes and plans, usually coming out ahead until - for some reason - he decides to go one on one with Superman. For the reflection, you have Batman and the Joker. Both geniuses, both plotters, both "normal" people who scare the bejeezus out of everyone else in the DC universe. On numerous occasions it has been shown that the Joker is where, but for the grace of god, goes Batman. (excuse the saying if it offends, it is simply a turn of phrase).
The point being, the nemesis should resonate with the hero/PC. That resonance is half the fun, and what gives the meetings so much extra energy as everyone else waits with baited breath to see what happens next.
Leaving a Mark
I mentioned this above in 'The Long Game', but a Nemesis should leave a mark on the PC, and in many cases should be marked in turn. The second part isn't completely necessary, but it helps to make the relationship reciprocal. Eitherway though, some mark needs to be left. The death of a loved one, a significant defeat, a scar on the face of an otherwise flawless duelist. Literature, movies, and tv shows are full of examples you can use. This is one of the harder things to do in a game as a set up, unless the PC is on board for it. Why? Because PCs tend to protect what is important to them. They also tend to kill the things that hurt them, and kill them violently. How you handle that is up to you, but there may be suggestions in that post linked above. I'm not sure though.
Play It Up
Finally, the big thing you need to do with a nemesis is to play it up. Let people know that while a certain PC may have many enemies, that this one right here is special. This one has something going for it, and is not like the others at all. The PCs will catch on to that, and will look a bit more seriously at this specially marked out NPC. Once you've done that, all that remains is to deliver on the promise. Go big, or go home. Especially since if you don't go big with this NPC, the PCs will likely send them home in a body bag.