I think this is a bug in the error message:
alvherre=> alter table test add column b int not null;
ERROR: Adding NOT NULL columns is not implemented.
Add the column, then use ALTER TABLE ADD CONSTRAINT.
However, there is no way to add a NOT NULL constraint to an existing
column in a table, so the error message is misleading.
alvherre=> alter table test add constraint bnotnull not null b;
ERROR: parser: parse error at or near "not"
--
Alvaro Herrera (<alvherre[a]atentus.com>)
"Siempre hay que alimentar a los dioses, aunque la tierra este seca"
(Orual)