Q:

Creating Non-Clustered Index on Non-Persisted Computed Column SQL Server

I am struggling to find any documentation on how SQL Server actually stores a non-persisted computed column.
Take the following example:
--SCHEMA
CREATE TABLE dbo.Invoice
(
    InvoiceID INT IDENTITY(1, 1) PRIMARY KEY,
    CustomerID INT FOREIGN KEY REFERENCES dbo.Customer(CustomerID),
    InvoiceStatus NVARCHAR(50) NOT NULL,
    InvoiceStatusID AS CASE InvoiceStatus 
                         WHEN 'Sent' THEN 1 
                         WHEN 'Complete' THEN 2
                         WHEN 'Received' THEN 3
                       END
)
GO

--INDEX
CREATE NONCLUSTERED INDEX IX_Invoice ON Invoice
(
    CustomerID ASC
)
INCLUDE
(
    InvoiceStatusID
)
GO

I get that it is stored at the leaf level, but if the value is not persisted how is anything stored at all? How does the index help SQL Server find these rows in this situation?
Any help greatly appreciated,
Many Thanks,
EDIT:
Thanks to Brent & Aaron for answering this, here's the PasteThePlan clearly showing what they explained.

A:

When SQL Server creates the index on the computed field, the computed field is written to disk at that time - but only on the 8K pages of that index. SQL Server can compute the InvoiceStatusID as it reads through the clustered index - there's no need to write that data to the clustered index.
As you delete/update/insert rows in dbo.Invoice, the data in the indexes is kept up to date. (When InvoiceStatus changes, SQL Server knows to also update IX_Invoice.)
The best way you can see this for yourself is to actually do it: create these objects, and execute updates that touch the InvoiceStatusID field. Post the execution plan (PasteThePlan.com is helpful for this) if you want help seeing where the index updates are happening.

A:

The value for an indexed, non-persisted computed column is not persisted in the data pages of the table, but it is persisted in the pages of the index. It remains non-persisted in the table, regardless of whether it is persisted in 0, 1, or multiple indexes.
Just to illustrate Brent's description, taking the example you gave, let's insert a row:
INSERT dbo.Invoice(CustomerID, InvoiceStatus) VALUES(1,N'Sent');

Now, let's see the index pages:
DBCC TRACEON(3604, -1);
DBCC IND(N'dbname', N'dbo.Invoice', 2);

(Obviously change dbname, and the index ID might not be 2 in your case.)
Output (yours will surely differ):

And finally, let's inspect the page for PageType 2:
DBCC PAGE(7, 1, 584, 3);

(You will likely need to change 7 to match your database id, and if you have multiple data files, you may need to change the second argument to match PageFID from the first result.)
Output:

That's on the index page.

A:

The attribute PERSISTED for a computed column relates to whether the values are persisted in the table (clustered index or heap) and not whether the values are persisted in the index.
The CREATE INDEX has the requirements for the limitations regarding computed columns and indexes:

Computed columns that are deterministic and either precise or imprecise can be included columns. Computed columns derived from image, ntext, text, varchar(max), nvarchar(max), varbinary(max), and xml data types can be included in non-key columns as long as the computed column data types is allowable as an included column. For more information, see Indexes on Computed Columns.

There is no limitation on whether the computed column is persisted or not.
and further (not about included but about computed columns in the main part of an index):

Indexes can be created on computed columns. In addition, computed columns can have the property PERSISTED. This means that the Database Engine stores the computed values in the table, and updates them when any other columns on which the computed column depends are updated. The Database Engine uses these persisted values when it creates an index on the column, and when the index is referenced in a query.
To index a computed column, the computed column must (be) deterministic and precise. However, using the PERSISTED property expands the type of indexable computed columns to include:
...

