I always nickname my team, and the Pokemon that I use for stuff other than battling too, like those with HMs, False Swipers, Cute Charmers, etc. It's usually random names, that have a subtle meaning too. Like Fournier the Talonflame, it's a motor glider, fitting for him as a Flying-type, and it's also a common French surname that means "baker", suitable for his Fire typing. I kinda went for French names on my X, so others are Miette the Greninja (also means "pearl"), Chantilly the Lapras (like the cream and castle), Armand and Marguerite the pair of Meowstic (characters in a Dumas novel), Baudelaire the Malamar (French poet), Marengo the Dragalge (Napoleon's horse). Aaaaaand lots more!
My most recent nicknames are for a competitive team I'm breeding right now. My theme is brands of foods and drinks, that also make sense for their appearance. Like Heinz the shiny Helioptile, because he looks like he's been drenched in ketchup; Pringles the Floatzel, because his tube thingy looks like a pringle; Pepsi the Toxicroak, because he looks like the pepsi logo and is a Poison-type {XD}