Vinyl with a laminate overlay will insure they last for a very very very long time.

You could also use Polypropylene with a laminate overlay. Whatever you do DO NOT put mylar over the vinyl. The mylar and vinyl don't have the same contraction and expansion rates so you would end up with curled, peeled, torn stickers. I deal with large scale printers for the decal sets that I produce. Not sure if local shops do this but I would assume they would. They have to print the art on the vinyl, then they have to pass the vinyl in a laminator, then they have to run it through the plotter to cut the stickers out.