@Amberlamps your question is very generic and from one perspective, AakashM did answer it in a comment already.
However let's look at it's basics to illustrate some ideas and techniques and their design considerations..
For a single user, what is the least amount of records (of the smallest size) that will address your need.
On the surface (m) records per user. However more carefully, you can see it is likely to be a sparse set or the opposite of it, i.e. a mostly filled set.
You can, based on your data, come up with more complex representations if space is your concern.. i.e. for each user represent all "seen" records in ranges, i.e. (user1, lowid1, highid1), (user1, lowid2, highid2), (user2, lowid1, highid1) and so on. Separately system wide you'd have a system lowid and system highid to give boundaries to your queries. In essence this is one way to represent a sparse set (I haven't seen this exact structure anywhere else but if someone has seen it formally represented elsewhere please comment)..
You can find other ways to represent sparse sets too.
OTOH, if speed of lookup is more important then a straight n:m takes extra space compared to other representations but gives you very high speed for almost any operation you can think of.
Now switching topics.. In relational DB;s Having a separate table is actually not much more overhead, because the storage is efficient.
In NoSQL DB, adding an array to each user will take less space, however when you're searching for all users who have "read" a particular notification, it forces you into an expensive query, unless you have indexes (which can be the same overhead as having them in a separate table). In this case if you switch the query around and search for all users who have "not" read a notification, it could be even more expensive.
Write a comment or update your question and I'll expand more if as needed.