Well, there are many options besides Choice Scarf/Band for Gallade, but if you must choose one, I would go with Band. Gallade is already pretty fast, but the Band on him makes him a real threat to other teams, especially when they are expecting Bulk Up or something. Here is a moveset that suits Gallade nicely with a Band.
Gallade @ Choice Band
EVs: 4 HP / 252 Atk / 252 Spe
Jolly (+Spe, -SpA) / Adamant (+Atk, -SpA)
- Close Combat
- Zen Headbutt
- Shadow Sneak / Stone Edge
- Night Slash
This Gallade is a threat to consider. Close Combat with Band can most definitely kill most Pokemon that don't resist. A 2HKO. Zen Headbutt is the other STAB move that can be pretty terrifing, too. Shadow Sneak is for finishing off Pokemon, and with Band they don't have to be terribly under-health. Stone Edge is coverage, and pretty powerful, along with Night Slash.
If you decide that you don't like Gallade, check out this Smogon page for other options, like Bulk Up or Swords Dance.