Change Permalinks

Every time I change my permalinks from default to anything else, all my links seem to break on the live site and I get a “page not found” message when they are clicked on. How do I change my permalinks without this happening?