How to add a column with a foreign key constraint to a table that already exists?

You just have to add another step - in fact PostgreSQL is already telling you that: column "sender" referenced in foreign key constraint does not exist.

The FOREIGN KEY (aka parent) column has to already exist in order to make it an FK.

I did the following (from here and the documentation). Note that the parent column has to have a UNIQUE constraint (or be the PRIMARY KEY) but it doesn't have to be NOT NULL. This is because NULLs are not equal to each other, nor are they equal to anything else - each NULL is considered UNIQUE in its own right!

CREATE TABLE x(a INT UNIQUE NOT NULL);

CREATE TABLE y(b INT);

ALTER TABLE y ADD COLUMN c INT NOT NULL
CONSTRAINT y_x_fk_c REFERENCES x (a)   -- if x (a) doens't exist, this will fail!
ON UPDATE CASCADE ON DELETE CASCADE;  -- or other Referential Integrity Action

A couple of points to note (see the fiddle here) - an attempt to insert a value into y (c) which is not in x (a) fails and the constraint name is given in the error message.

The fiddle has NOT NULL constraints on x (a) and on y (c). Unless I have a really compelling reason, I always declare my columns as NOT NULL - it helps the optimiser and reduces the potential for confusion/error. You can experiment yourself with the fiddle to see what happens when you leave out the NOT NULL on either (and both) field(s) - the behaviour isn't always intuitively obvious!

ALWAYS give your foreign keys meaningful names. Being told that key "SYS_C00308108" is being violated is not very helpful. See the fiddle here for Oracle's behaviour under these circumstances the key name will vary from fiddle to fiddle, but is some arbitrary string beginning with SYS_... (comes after the long dbfiddle generated tablename).

Evan Carroll in his answer here believes that auto-generated names are OK - I've shown why that is not a good idea for Oracle (at least up to 18c), but I also feel that it's not a good idea for PostgreSQL either - potential problems for portability if nothing else.

I would like to credit Evan Carroll for pointing out that the addition of the new field and the FOREIGN KEY creation and the CONSTRAINT (with specified name) can be added in one step and not two steps as I originally said) - so please give him credit for that if you feel like upvoting me - I do go into more detail however.

Considering the statement in your question:

ALTER TABLE message ADD FOREIGN KEY (sender) REFERENCES users;

It would be a "nice-to-have" if the RDBMS could automatically create the field you want with the data type matching the referenced field.

All I would say is that changing DDL is (or at least should be) a rarely used operation and not something that you'd want to be doing regularly. It also risks adding to an already fairly substantial documentation.

At least PostgreSQL tries to do something reasonable - it concatenates the table name, the FOREIGN KEY field name and fkey. Furthermore, when you do name the constraint yourself, the error message will add DETAIL: Key (c)=(7) is not present in table "x". to give something that might make sense to a human being (unlike Oracle - see the end of the PostgreSQL fiddle).

I'm not sure why everyone is telling you that you have to do this in two steps. In fact, you don't. You tried to add a FOREIGN KEY which assumes, by design, the column is there and throws that error if the column is not there. If you add the COLUMN, you can explicitly make it a FOREIGN KEY on creation with REFERENCES,

ALTER TABLE message
  ADD COLUMN sender INT
  REFERENCES users;  -- or REFERENCES table(unique_column)

Will work fine. You can see the syntax of ALTER TABLE here,

ALTER TABLE [ IF EXISTS ] [ ONLY ] name [ * ]
action [, ... ]

With "action" as,

ADD [ COLUMN ] [ IF NOT EXISTS ] column_name data_type [ COLLATE collation ] [ column_constraint [ ... ] ]

These examples are even in the docs,

ALTER TABLE distributors
  ADD CONSTRAINT distfk
  FOREIGN KEY (address)
  REFERENCES addresses (address);

ALTER TABLE distributors
  ADD CONSTRAINT distfk
  FOREIGN KEY (address)
  REFERENCES addresses (address)
  NOT VALID;

But all that isn't needed because we can rely on autonaming and the primary-key resolution (if only the table-name is specified then you're referencing the primary key).