In Erwin Brandstetter's correct answer, he explains that you should indeed be seeing the behavior you want (multiple NULLs allowed in a Unique constraint). You should see this behavior in Postgres in particular as well as any SQL standard compliant database in general.
However, the Postgres doc cautions about portability because some databases are known to be in violation of this feature. For such a non-compliant system I suggest replacing the use of a NULL value in such fields with a bogus value. The bogus value would be a string such as "unknown_" plus some arbitrary value that is virtually certain to be unique. That arbitrary value could be something like the current date-time plus a random number.
But, rather than roll your own arbitrary value, generate a UUID. The original Version 1 UUID is indeed a combination of the current date-time, a random number, and the computer's virtually unique MAC address.
A UUID presented as a hex string with canonical formatting using hyphens looks like this:
So my suggestion is to combine an arbitrary string such as "unknown_" plus a UUID, to look like this:
So my suggestion for non-compliant databases is to generate such a value and use it in place of NULL, use it where you do not yet have a known value in that column for a particular row. Instead of writing queries that look for rows that have (or do not have) a NULL value in that column, write queries that look for rows that have (or do not have) a value beginning with the arbitrary string, "unknown_" in this example. Each row would then satisfy the constraint of having a unique value.
Indeed, I would assign this "unknown_" + UUID value as the default for that column.
You could also add a NOT NULL constraint to this column.
Postgres has built-in support for the data type of UUID, but that's irrelevant in this answer here. What you need is to generate a UUID value.
For generating UUIDs you need an extension (plugin) that adds this capability to Postgres. Most Postgres installers include such an extension. This extension is called uuid-ossp. Usually the extension is not activated by default. To do so in recent versions of Postgres, use the CREATE EXTENSION command. For instructions, see my blog post on installing in Postgres 9.1 and later or my other post on Postgres 9.0 and earlier. Both the new and old way of installation is easy provided the extension/plugin was compiled and bundled with your Postgres installation.
Let me be clear that for Postgres alone, there is no need for this workaround because Postgres complies with the SQL standard. But if:
…then a workaround such as this is necessary.