Permalinks – converting from default to anything else

I left permalinks at the default setting, but not I want to have some structure. I tried just switching the settion, but naturally it broke all the post links in the category list.

What do I need to do to switch from the default setting to one that uses the directroy structure ?

Thanks,
Joe Gibbs