Battle Moveset

A Good Moveset for Cleffa would have to be this:

Attacks:

Attract
Toxic
Protect
Substitute

Items Attached:

Leftovers

Preferred Nature:

Impish

Strategy Using Cleffa

Lets face it, Cleffa is stuck with some of the worst stats in the game. With its poor speed and poor defense, this pokemon will probably not last a turn to even use this moveset, which could be said for any moveset you give to Cleffa. Its special stats aren't that good either, any decent special sweeper would knock out Cleffa.
With this moveset, and a little bit of luck, you should be able to start of with either Toxic or Attract. Try to get your opponent poisoned with Toxic as soon as you think Cleffa will be able to do so, even if it means there is a chance Cleffa will get knocked out. Then alternate turns with Substitute and Protect(when you use Substitute and Protect should be decided by yourself and when you think it will work well) to let the toxic take effect on your opponent while you are able to survive a few turns.
The nature is to boost its defense while losing out on one of its unused stats. The EV's are mainly focused upon increasing Cleffa's poor defense, even though it won't do much good, you may get lucky. If you do not agree with these, you can easily put max EV's into HP instead of Defense.
For its ability, it can only be Cute Charm which sucks on this pokemon, 30% chance of your opponent being attracted by a Physical attack, will it survive the attack? Probably not. I would advise that Cleffa is better suited on a fun team and really shouldn't be used in competitive battling.

EV Corner:

Max out the EVs in Defense for Cleffa with any remaining in HP & Special Defense

Strategy Against Cleffa

Cleffa's Special Defense is Average but it's Physical Defense is really poor...so attack it with Physical Attacks or Fighting type Attacks and it'll be gone in no time

Contest Moveset

A good Contest Moveset for Cleffa would have to be this for the Cute Contest best with Timid, Hasty, Jolly or Naive Nature:

Attacks:

Sing
Rest
Attract
Encore

Items Attached:

Pink Scarf

Strategy Using Cleffa

If you do the attacks in this following order you should have very few problems; 1st - Sing, 2nd - Rest, 3rd - Attract, 4th - Encore, 5th - Sing

Locations in Games

Ruby/Sapphire Trade from FR/LG Colosseum Trade from FR/LG Fire Red/Leaf Green Breed Clefairy/Clefable

Animé Appearences

Cleffa has had two Animé Appearences. First it was in Millennium town with the Pichu Bros. After that one fell out of the Clefairy's space ship and Ash & Co. decide to help it. Short 3: Pikachu & Pichu! Episode 248: Wish Upon A Starshape!