What happens at the data page level when the record length changes
how a DBMS (SQL Server 2008 R2 and others) handles adding a column to the end of a huge table so quickly.


Well, there is a false assumption here, that being that adding a new column is always done quickly. This is not a true statement.

Now, when adding a column that allows NULLs, that can be done quickly as the meta-data of the Table definition gets updated but the NULL isn't physically added to the datapages in that moment. SQL Server can return the correct NULL to queries since it is logically obvious what the "value" is. When rows are inserted or updated, the records that are written to the datapages do include the NULL (for fixed-length columns, unless the SPARSE option was used for the new column or Data Compression is enabled on the Clustered Index). But the rest of the rows that have not been updated will not have the NULL physically added until an index REBUILD.

However, when adding a column marked as NOT NULL, then, prior to SQL Server 2012 (and even then, only if the new value was a runtime constant), then the actual value was written physically to the datapages in that moment, and that operation could take a looooooooooong time, depending on how many rows and/or how much data was in the table. You can find plenty of questions and articles about trying to overcome this issue as tables with many GBs of data and/or hundreds of millions of rows could take hours to add a new NOT NULL column.

Then came a truly wonderful new feature in SQL Server 2012 (Enterprise Edition-only, which also implies Developer Edition) whereby adding a new NOT NULL column with a default value could be an instantaneous, meta-data only operation, just like adding a column marked as NULL. The only caveats are that the datatype not be a LOB (e.g. MAX-types, XML, etc) or CLR-based type, and that the value be a runtime constant (i.e. mainly literal values). Something like NEWID() would not be instantaneous since it would need a different value per each row. But for values that are runtime constants, SELECT operations can easily get the correct value by just looking at the meta-data of the DEFAULT which gives the logically-obvious value.

The MSDN page for ALTER TABLE, in the Locks and ALTER TABLE section (under "Adding NOT NULL Columns as an Online Operation"), talks about this behavior.