Easiest way is to just create a CCK field, a checkbox, that you can then add to your product template (use Contemplate) that, when the field is active, shows a "NEW" icon.
Unless you wanted to write a few lines of code within the template to check the current date, and if it's within a certain threshold, to show said icon. That wouldn't be too hard, I don't think.
EDIT: Off the top of my head, you could put something like this into a template. This will show a product as "New" for the first week after it's been published.
<?php
$created = db_result(db_query("SELECT created FROM {uc_node} WHERE nid = %d", $node->nid));
$curTime = time();
if ($curtime - $created <= 604800) print "NEW!";
?>Not tested but I imagine it'd work, or work with some tweaking. Might be a cool feature to add, or expand upon in a Contribution. Variable time threshold for display, etc.
Joined: 08/14/2007