How can I add a column that doesn’t allow nulls in a Postgresql database?

I’m adding a new, “NOT NULL” column to my Postgresql database using the following query (sanitized for the Internet):

ALTER TABLE mytable ADD COLUMN mycolumn character varying(50) NOT NULL;

Each time I run this query, I receive the following error message:

ERROR:  column "mycolumn" contains null values

I’m stumped. Where am I going wrong?

NOTE: I’m using pgAdmin III (1.8.4) primarily, but I received the same error when I ran the SQL from within Terminal.