I also found Wampus' link to be extremely interesting (even inspiring).
It does occur to me though, Halivar, that the true Sandbox campaign is usually quite different to play and not just to DM. Sandbox games fit well with kick-in-the-door, monster-mash, treasure-grab players and may not be as fun for players who like being part of a big story--an overarching narrative. But if you're afraid that you've been so linear that your railroading, I understand the need for a shake-up.
It sounds like you've been running more linear, story-based campaigns, and if they've been coming back to your table again and again, they may like it that way. If you've been hearing complaints, then I see the need to change styles, but just be careful that a sandbox game ("Go wherever you like! There are 101 equally important hooks and threads all over!") is what they are looking for.
I say this only because I tried switching to a sandbox style with one of my groups once (after ending a 2-year campaign that ran like an adventure novel). After a couple of sessions where I just laid out the map (not literally) and let them explore and discover freely, one of the players came to me and said, "So when do we get to the story?" I told them they needed to make their own story: Get famous! Get rich! Depose the evil king! Start a war! Forge peace! Collect enough dragon tears to make the Potion of Eternal Life!
To my suprise, they all hated this approach, and often sat at the table asking, "So what do we do now?"
I think this might have been a peculiar set of players, so there may be nothing to worry about in your case. Just make sure that a new type of game world is what will be most fun for the folks at your table.