I thought it was Thursday, because that is when the featured page gets updated.

However, I don't think Apple has a set release day because new apps go into the store every day. Which implies to me that they simply get released when Apple is done reviewing the apps.

New apps generally appear late at night with the next day's time stamp, so check around 10pm PST.