I love Gallade. Too bad its not fast enough to handle the current metagame.
Both abilities are pretty good. Just remember that Steadfast gives that much needed increase in Speed.

Bulk Up
EVs: 252 Attack and speed, 4 HP
Nature: Adamant/Jolly
Ability: Steadfast (Justified is illegal on this set)
@: Life Orb/Leftovers

Bulk Up
Drain Punch
Psycho Cut/Stone Edge/Ice Punch
Shadow Sneak

Combining Bulk Up with Gallade's high special defense will make him something tough to take down, especially with Drain Punch. Shadow Sneak is a priority move. Your last choice is a secondary STAB or a coverage move.

Swords Dance
EVs: 252 Attack and speed, 4 HP
Nature: Adamant/Jolly
Ability: Either
@: Life Orb/Leftovers

Swords Dance
Close Combat
Psycho Cut/Stone Edge/Ice Punch
Shadow Sneak

I don't feel the need to explain this.

Choice Band
EVs: 252 Attack and speed, 4 HP
Nature: Adamant/Jolly
Ability: Either
@: Choice Band

Close Combat
Shadow Sneak
Psycho Cut
Stone Edge/Ice Punch

You should know how it works.

Choice Scarf
EVs: 252 Attack and speed, 4 HP
Nature: Adamant/Jolly
Ability: Either
@: Choice Scarf

Close Combat
Night Slash
Psycho Cut
Stone Edge/Ice Punch

You should know how this one works too.

Other options:
Gallade has a healthy supply of support options.
Hypnosis causes sleep with crap accuracy
Will-o-wisp is burn inducer
Thunder Wave paralyzes.
Gallade's other attacks are noteworthy.
Zen Headbutt is an option over Psycho Cut.
Thunder Punch can hit Gyarados hard
Fire Punch takes down Scizor
Leaf Blade disposes of Gastrodon and Golurk.
X-Scissor has more power than Night Slash when dealing with Lati@s.
Earthquake is pretty stupid.