What structural property creates stickiness? Recently, me and my mom parked her car in a spot reserved for customers of a super expensive shoe store while going to get some also fairly expensive drinks at Starbucks. When we came back, an employee at the shoe store put a sticker on my mom's window warning us he could have us towed and ticketed. Clearly they're bitter about having no customers. This sticker left a whole bunch of sticky residue on the window.

I knew from experience that water wouldn't get the job done, so I put some canola oil on a paper towel and sure enough the sticky residue dissolved into the oil and I could see it dissolved in the liquid on the paper towel.

This got me thinking. Is it generally true that a sticky substance will be nonpolar? Furthermore, is there a generalization which can be made about structures which are sticky on a macroscopic level?

My only guess is that sticky substances are usually viscous too which leads me to believe that there must be a lot of VDW/dispersion interactions involved in those materials because I understand that high viscosity is related to strong intermolecular attractions. Although, the viscosity argument doesn't work for sticky solids (unless you say that a sticky solid is actually just an extremely extremely viscous liquid).
Long story short, no, sticky substances don't have to be nonpolar at all. Pour a little wine or beer on a table, and let it dry almost completely: it will get sticky, but still be water-soluble and hence polar. Also, there are certain water-based glues, which are surely sticky and polar. On top of all that, go read about the hagfish, only make sure you're not eating at the moment, for fear of adverse reaction.

As for the structural properties that make a substance sticky (or viscous, which is basically the same thing), these are not so easy to point out. Many sticky things are polymers, i.e., very long molecules with lots of van der Waals interactions, just like you said, and probably lots of interactions of other sorts, too. But this is hardly a rule, as exceptions both ways are plenty. Polyethylene is a polymer, but is not sticky at all. On the other hand, sugar syrup can be pretty sticky, despite containing no polymers.

As for the sticky solids, I would claim that there are none. Of the possible examples, some are actually highly viscous liquids, some are sticky because they are covered with such liquids, and some would stick to things because of electrostatic effects.