You can easily do this with CS-Cart. The site you refer to is just using options for their product. I have found that product options are real easy to set up and use. There are even ways to change what the product looks like based upon the options. You can also set up your options to only be compatible with other options.
One other thing to consider and it would take some checking is that there was some talk on the forum a while back about using flash to allow a customer to build a t-shirt. I believe the flash program was going to allow a base t-shirt to be changed color, size, and allow the customer to put their own text on the t-shirt. I think that all this was going to be changed while displaying the changes as an image on the screen. Even thought this was supposed to be for t-shirts I am sure you could adapt this for you stickers.
Either way, whether you use options or find out more about the flash program you can easily do what you want to do using CS-Cart.
Brandon