How do I create a unique constraint that also allows nulls?

What you're looking for is indeed part of the ANSI standards SQL:92, SQL:1999 and SQL:2003, ie a UNIQUE constraint must disallow duplicate non-NULL values but accept multiple NULL values.

In the Microsoft world of SQL Server however, a single NULL is allowed but multiple NULLs are not...

In SQL Server 2008, you can define a unique filtered index based on a predicate that excludes NULLs:

CREATE UNIQUE NONCLUSTERED INDEX idx_yourcolumn_notnull
ON YourTable(yourcolumn)
WHERE yourcolumn IS NOT NULL;

In earlier versions, you can resort to VIEWS with a NOT NULL predicate to enforce the constraint.

SQL Server 2008 +

You can create a unique index that accept multiple NULLs with a WHERE clause. See the answer below.

Prior to SQL Server 2008

You cannot create a UNIQUE constraint and allow NULLs. You need set a default value of NEWID().

Update the existing values to NEWID() where NULL before creating the UNIQUE constraint.