Don't actually do Gannondorf's record, though, it freezes the game (anything over 4500 or so will).
I'm not good at all that fancy stuff either. The most I've gotten is with Yoshi, over 2,000. Use a short jump with down-A until the last second, then smash it with the bat (if you're lucky, you can pull off four down-A attacks before using the bat). Try to have Yoshi land just barely to the left of the sandbag's center, to push it over a little bit every time.
I think I was able to get over 1,300 with Roy. Up Smash until 4.5 seconds remain, then charge his Sheild Breaker (hold B).
Interesting note: If you stand directly next to and face away from the sandbag with Pichu or Pikachu, and then smash attack (with the bat, of course) toward it, it will fly farther than if you were facing it the whole time.