What does it mean for a particle to have volume? As far as I understand, we do not know whether an electron is a point particle or not, but we have a very low upper bound for its potential volume. If it turns out that electrons do have volume, what exactly does that mean? What constitutes this volume and how does it compare with the classical notion of volume?
 A: 
As far as I understand, we do not know whether an electron is a point particle or not, but we have a very low upper bound for its potential volume. 

It depends what one means by low, physics is not a hand waving discipline. There exist experimental limits as seen in this answer to a related question. It is a low limit with respect to its black hole horizon , but very stringent with respect to laboratory measurements.
In addition, the very successful and predictive standard model of particle physics , depends on the postulate that all elementary particles in the table  are point particles.
Postulates are the physics axioms that pick up the subset of mathematical solutions of the equations in the physics models which are relevant to the data and observations. The mathematical successes of the model are quite high as seen in the recent LHC experiment, and thus there is no need to worry about the point nature of the particles.

If it turns out that electrons do have volume, what exactly does that mean?

It means that the postulate of "point particles" has to be changed to accommodate new data and still keep the successes of the previous measurements and observations. Newtonian physics still works fine in its dimensional region of validity, even though we know it emerges from an underlying  quantum mechanical frame work and at large dimensions is superseded by General Relativity.

What constitutes this volume and how does it compare with the classical notion of volume?

This is for a hypothetical case,  the limits given from experiments  are for a classical volume in three dimensional space d(v).
At the moment string theories postulate a one dimension extension, from a point to a line . A line still does not have volume, so it is all a matter of theoretical conjecture for distances smaller than the Planck length .
On the experimental side:in quantum mechanics volume can be gauged by interactions and interactions are bound by the Heisenberg Uncertainty principle and are momentum dependent. That is why the concept of "crossection" exists. It gives the interaction "area" for a given momentum. In this sense the "area" of an electron can be bounded and this is what the experiments utilize in setting the limits.
