You can do this via custom code using EntityFieldQuery if you want, but I actually think you can manage this via Views. If you're showing this on the product display, you can create a Views block that only appears on those pages and uses the node ID as a contextual filter. If this is over your head, you may need to research Views a bit. : )
Once you have that in place, you can join from the display node to the referenced product to line items referencing this product. With Views aggregation enabled, you can then SUM the quantity of all line items referencing that product to determine how many times it's been ordered. You'd filter this to only line items on completed orders by joining from the line item to the order table and filtering on the order status.
For an example of this sort of functionality, you can look at Commerce Reporting, which has a product report with the exact same functionality, just as a general list showing all products purchased on the site.