Nature doesn't seem to matter as much to me, really. There is always EV training, or whatever. I'd stick with Quirky, Docile, Bashful, or Serious nature, since it isn't stat-hindering.
So, really, you want the Skill Link ability. If it doesn't have it, then go for Cute Charm...
Skill Link: Makes multi-hit moves go 5 times.
Cute Charm: If it it physically hit by a pokemon of the opposite gender, then they may become attracted.
Technician: Boosts weaker moves. I guess it goes good with Tail Slap, because it might boost each hit up to about 40. Five hits, and that's about... 180? (Of course, I might be doing this wrong, because that does sound a bit... Too good.)
So, since Cinccino has rather high attack (alot higher than it's Special), use physical moves.
Use this moveset:
Tail Slap: Has base power of 25, and can hit up to 5 times. If it does, that is base power 125. That's alot. And if you have Skill Link, it should always hit 5 times.
Return: Always a strong move if it has high happiness. Plus, since it's another Normal type move, it is powered up.
Sing: It always helps to put an opponent asleep. Even though it may never hit, you'll be glad when it does.
Wake-Up Slap: Goes good with Sing, as it does double damage when the foe is asleep. This move is fighting type too, so it helps with Rock, Dark, Ice, and even Steel types.
All of the above except Return is learned by leveling up. Return is a TM you can buy in Ninbasa City for 10,000.
Hope this helps. I'm sick of people calling this thing weak. Mine took out most of the Elite Four at level 70, and it doesn't even have the Skill Link ability. ;)
Oh right, and as for a hold item... Use a Silk Scarf since it has those two Normal type moves, or use Scope Lens so each of those Tail Slaps have a chance of getting a critical hit. c: