We really should point out the difference between flash accessories that actually soften the light themselves (a softbox) and accessories that are meant to be used while bouncing the flash off of something (pretty much everything else).
To actually soften light, you can do two things; make the source bigger or move the light closer to the subject....that's it. Just putting a translucent material over the flash, won't make the light softer, unless it significantly increases the size. So even that softbox I linked to, really only does much good when you are rather close to the subject.
As most of the other accessories are meant to assist while bouncing, it would be beneficial for you to understand the ins and outs of bouncing a flash. As mentioned, some people just point the flash behind them and that's it....no accessories required. The main benefit of most of these, is that they split the light, allow some to go forth and bounce (off a wall or ceiling) but also sending some forward, directly to the subject. This is good, because the direct light fills in the shadows caused by the light coming from the bounce surface. A good example of this is the Lumiquest Promax system with it's 80-20 unit. It allows 80% of the light to go out and bounce, while deflecting 20% of it forward for fill. I've got the promax system but don't use it much because it's not as useful when the flash is horizontal rather than vertical. It's great when the flash is always vertical though.
So if you do have a good handle on bouncing the flash, then all you really need is a simple bounce cards, because most of the accessories do pretty much the same thing.
Lastly, I think that it's important to recognize when your flash accessory won't be helping you...and when it will be actually hurting you. This is, I think, the most overlooked part of using these things. I've seen many, many professional photographers using these things in situations where it's utterly pointless to be using them.
You should not be afraid to use bare flash when your accessory won't be of use. This is another reason I like the Demb unit, it's got a nice hinge, so I just fold the card back and out of the way and use bare flash when I need it.
A flash head is (or is similar to) a Fresnel lens...it directs the light out in a beam. This is what gives these small flashes their great range. I read somewhere that a Canon 580EX (bare) can put out similar light to an Alienbee B800 light (with standard reflector). However, if you put a diffusion material in front of them, the flash unit is now several stops behind the studio light...I assume it's because when you diffuse the light, you destroy the beam properties from the flash head.
So by using bare flash, you have a great range and you're not working the flash nearly as hard as you do when it's bounced & diffused. This lets the flash recycle faster, which gives you better opportunities for getting the shot...and it also makes your batteries last longer.
Of course, the key is knowing when your accessory will help and when it won't.