I love to experiment with packaging and haven't settled on one thing yet... but I have found that Dollar Tree has rolls of tulle for $1 (it's the dollar store you know), and I have wrapped soaps in this and tied a bow at the top.
Dollar Tree (it's my favorite, can you tell?) also has little pillar holders in two colors (bronze and white) and they are perfect for a single bar of soap and could serve as a soap dish. I wrap in cellophane sheets and put a sticker on the bottom to hold it. I use paper shreds (or make my own from grocery sacks with a crimper and shredder). I was a scrapbook junkie (before jewelry and soaps) and have lots of paper left over, so once I wrap the soap and dish with the cellophane, I also wrap about a 1/4" strip of paper around the soap and top off with one of my square stickers. The type of soap determines the type of paper/pattern I use.
I'm interested to see what others are doing... I'm new at this so still looking for ideas, too.