Although I never bothered with it in the first two generations, since I started with Sapphire, I've always decided to nickname my Pokemon, sans legendaries. I guess I always compared leaving a Pokemon without a nickname to something like having a cat named Cat.
As for what I nickname them, it depends on my mood. I've tried everything from using anagrams of a Pokemon's name (give or take a letter), using their name in a different language, or something like that. And yes, I have transfered my Pokemon from one game to another, with half of my current White 2 party coming from either HeartGold or the original White.