I've come up with nicknames for my Pokemon Yellow team, which I'm currently playing:
BOLT (Pikachu) - Pretty straight forward, Pikachu is know for its speed, and being an electric type it just fits. It's a Pikachu, no need to be too picky.
RAFFLUS (Venusaur) - From the scientific name of the Kerubut flower, Rafflesia Arnoldii. Looks kinda like the flower Venusaur has on its back. This one actually took long to come up with.
ARAGON (Charizard) - A mix between Eragon (from the novel) and Aragorn, the heir to the throne of Gondor. Just sounds like a dragon name, even if Charizard isn't a true dragon.
NOBLE-FIVE (Blastoise) - Noble-Five is a member of Noble Team in the Halo Universe. He is a Spartan II supersoldier, characterized by his large build and wielding large weapons.
AQUILES (Pidgeot) - A mix between the Roman a word for eagle, Aquila, and the Greek Hero Achilles. A true warrior indeed.
HYPERION (Rhyhorn, eventually Rhydon) - Hyperion was one the 12 Titan children of Gaia. With Rhydon being such a beast, the name just came up and it fit so well.
I've also chosen permanent nicknames for specific Pokemon for all my games, for example:
SPAWN (Umbreon) - Spawn, if you don't know, is an antihero in the comics world. Not that I'm a fan, I just know he's supposed to be, basically, a knight of hell, with dark powers. So there you go.
TOOTHLESS (Dragonite) - Haha, I mean, tell me it doesn't fit... Toothless from "How to Train Your Dragon" is a dragon. Dragonite doesn't have teeth for all I know. Bam, instant win.
NESSIE (Lapras) - Loch Ness Monster. It's what Lapras was designed from. Nessie sounds like a ladie's name, so I always try to get a female Lapras.
METALSLUG (Steelix) - Metal Slug is an arcade game. But has nothing to do with Steelix, except for the fact that the name just fits; Metal=Steel, Slug=Snake.
IRON SKY (Skarmory) - Generic, straight forward and fitting. Thought about it after watching the cheese movie of the same name with the Nazis in the moon taking over the world and stuff.
MURAMASA (Scizor) - I got Muramasa from the name of the Ultimate weapon for the Ninja class in Final Fantasy III (DS version). Masamune is the second strongest weapon, perfect fit for Scyther.