You would have to loop through that customers orders and check each line item,
If you do this only in liquid this can significantly decrease theme performance if a customer has a lot of orders since you'd be running this operation on every single load of a product page.
So it would be best to have a max threshold at which point you use an ajax method to do the check on the clientside for logged in customers.
This information could be set in a cookie or web storage and do the marking on the clientside as well.
Any assumed performance hit would only be for logged in customers that have alot of orders.
Prices will vary and the theme used is a factor as is the level of sophistication needed(ajax fallback,cookies,etc).
Senior designers should be able to implementation a simple version in an afternoon since they still have to dig through the theme for all the places a product might be displayed.
Then there's the actual design of the messaging to the customer on the products.
I can be emailed(in signature) or forum PM'd with details for an estimate