I nickname everyone I train, starting out unimaginative (Meet BLAZE the Blaziken, guys) and eventually getting better (REQUIEM THE KYUREM LAYS WASTE TO YOUR ARMIES).
Some get "human" names (James the Luxray, Rory the Arcanine, Heather the Breloom...), some get more obscure human names (Siobhan the Ninetales, Izumi the Mienshao...) some get mythological/historical/literary names (Dante the Charizard, Amphitrite the Samurott, Ishtar the Cofagrifus...),and some get references to other video games in the form of names (Kain and Cecil, the duo of Zekrom and Reshiram; Volug the Mightyena, Cloud the Manectric...).
I once tried nicknaming everything I caught, but I started running out of names and wound up staring at my DS while trying to think of something I hadn't already used.