More or less what Benny said, with a couple additions: since you're working with content, remember that blocks of content are affected by actions and may be affected by other content, so in your case, new is relative to other content.
With that in mind you must consider these variables that affect your content (in your specific case, there might be a lot more in other cases):
an obvious one, since it will dictate the items per page and subsequent navigation
This is important and sometimes overseen: what's the point of adding selling techniques to something that doesn't exist? Yet I see it every day. If you don't have it, don't worry about new or affirmative selling techniques. Instead, you can inform the user when the item will be available again.
- frequency of updating and number of updates
Like Benny said, this makes a huge difference. If you update every day is one thing, if you update once a month, is another. But also keep in mind you could be adding 1 item a day or 300 items once a month. The difference is obvious.
- average days between visits per user
This is something easy and a metric you should be using anyways. For example, let's say your average user visits your site once a week. Then 7 to 10 days (assuming you don't update a lot) should be enough. If you update a lot, you could use progresive messages like "new", "added 3 days ago", "last week" and so on (you'll get the idea, copy is on you)
This is something you should research and track. Personally, when I do ecommerce sites or catalogs, I like to leave AT LEAST one row with no added value tags to reinforce the other items. So, once I consider the points above, I try to make room for at least 1 row. For example, let's say I get an optimum result of 16 items with "new" message. Then, if I use a 3 columns grid, I make the page to be 7 rows (since last "new" item will be in row 6). If I use 4 columns, then 5 rows. This is important for me, because I'd rather restrict "new" (or whatever) tags if the page becomes too long. I never have a "new" item in a second page, but again, this is what I DO
Finally, one point I consider and has nothing to do with UX, but since I come from marketing areas, I consider useful: do you REALLY need the new tag? Keep in mind this is a reinforcement on the sale funnel, so you might be prioritizing selling 1 candy just because it's new instead of selling a car. Rather than "new" I'd use "featured" items. but again, this is my personal view.