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

You have to set a default value.

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

... some work (set real values as you want)...

ALTER TABLE mytable ALTER COLUMN mycolumn DROP DEFAULT;

As others have observed, you must either create a nullable column or provide a DEFAULT value. If that isn't flexible enough (e.g. if you need the new value to be computed for each row individually somehow), you can use the fact that in PostgreSQL, all DDL commands can be executed inside a transaction:

BEGIN;
ALTER TABLE mytable ADD COLUMN mycolumn character varying(50);
UPDATE mytable SET mycolumn = timeofday();    -- Just a silly example
ALTER TABLE mytable ALTER COLUMN mycolumn SET NOT NULL;
COMMIT;

Since rows already exist in the table, the ALTER statement is trying to insert NULL into the newly created column for all of the existing rows. You would have to add the column as allowing NULL, then fill the column with the values you want, and then set it to NOT NULL afterwards.