How does SQL Server store more than 4000 characters in NVARCHAR(max)?

Yes it is possible - according to the MSDN documentation:

nvarchar [ ( n | max ) ]

Variable-length Unicode string data. n defines the string length and can be a value from 1 through 4,000. max indicates that the maximum storage size is 2^31-1 bytes (2 GB). The storage size, in bytes, is two times the actual length of data entered + 2 bytes. The ISO synonyms for nvarchar are national char varying and national character varying.

So if you specify nvarchar(max) you can store up to 1 billion 2-byte Unicode characters. That's Leo Tolstoj's War and Peace well over a hundred times over ....

SQL Server stores those max columns into special structures internally, which makes it possible to get around the 8K limit of the SQL Server pages. It works - but it's more effort than just storing a few hundred bytes on a page, so this storage system does pose more strain on SQL Server - use it with care, use it only when you really need to (and most definitely don't just make all your columns (n)varchar(max), just because you're lazy!)

Check out this really good article on Simple Talk: What's the Point of Using VARCHAR(n) Anymore? - it explains very nicely how (max) datatypes are different and less suited for smaller strings - use only when really needed!