There's a fascinating article in Fine Homebuilding # 221, pg. 73, where they torture test various brands of sandpaper discs and find that there's a HUGE gap in performance between the stuff that you can buy at Lowe's (Gator) and the stuff you can find only at good woodworking/tool stores or online (Mirka and Klingspor). I've typically used Mirka when I can get it; I will be trying some of the Klingspor discs soon since it was rated so much more highly. They also rated 3m highly, but didn't look at things like sanding sponges or normal block sanding paper, they just looked at discs.
There's three different things that seem to go into it. First, the quality of the abrasive. Cheap abrasive (Gator) will not hold the sharp 'edges' that make sandpaper feel gritty very long. The second is if there are any additional coatings. Norton, Mirka, and Klingspor have a Stearate coating that keeps the discs from loading up with the dust and grime from the object you're sanding. As auujay mentioned, there is a difference in the paper -- most used "C" grade paper, where Klingspor uses the "F" grade paper, which is much stiffer, but that seems to be the least of the issues with the sanding discs.
I should note that I've had really bad results with the Norton "universal" 5/8 hole disc design -- it seems to leave a lot of orbiter marks.