How do I add a composite check constraint that references a composite key?
A check constraint that references another table like that is called a FOREIGN KEY. You can do what you want with MATCH FULL

As a special note the types must be the same, so in your example tasks.users_id is text. It must be int (the underlying type of users.id).

CREATE TABLE users (
  id               SERIAL,
  name             TEXT NOT NULL,
  email            TEXT NOT NULL,
  organization_id  int,
  PRIMARY KEY (organization_id, id),
  UNIQUE (name, email)
);

CREATE TABLE tasks (
  id               SERIAL PRIMARY KEY,
  organization_id  int  NOT NULL,
  users_id         int  NOT NULL,
  description      TEXT NOT NULL,
  FOREIGN KEY (organization_id, users_id)
    REFERENCES users (organization_id, id) MATCH FULL
);


You can add the constriant after the fact like this..

ALTER TABLE tasks
  ADD CONSTRAINT asdf
  FOREIGN KEY (organization_id, users_id)
  REFERENCES users (organization_id, id)
  MATCH FULL;