CONSTRAINT to check values from a remotely related table (via join etc.)

A CHECK constraint is not an option if you need joins. You can create a trigger which raises an error instead.

Have a look at this example: http://www.postgresql.org/docs/9.1/static/plpgsql-trigger.html#PLPGSQL-TRIGGER-EXAMPLE

CREATE TABLE emp (
    empname text,
    salary integer,
    last_date timestamp,
    last_user text
);

CREATE FUNCTION emp_stamp() RETURNS trigger AS $emp_stamp$
    BEGIN
        -- Check that empname and salary are given
        IF NEW.empname IS NULL THEN
            RAISE EXCEPTION 'empname cannot be null';
        END IF;
        IF NEW.salary IS NULL THEN
            RAISE EXCEPTION '% cannot have null salary', NEW.empname;
        END IF;

        -- Who works for us when she must pay for it?
        IF NEW.salary < 0 THEN
            RAISE EXCEPTION '% cannot have a negative salary', NEW.empname;
        END IF;

        -- Remember who changed the payroll when
        NEW.last_date := current_timestamp;
        NEW.last_user := current_user;
        RETURN NEW;
    END;
$emp_stamp$ LANGUAGE plpgsql;

CREATE TRIGGER emp_stamp BEFORE INSERT OR UPDATE ON emp
    FOR EACH ROW EXECUTE PROCEDURE emp_stamp();

CHECK constraints cannot currently reference other tables. The manual:

Currently, CHECK expressions cannot contain subqueries nor refer to variables other than columns of the current row.

One way is to use a trigger like demonstrated by @Wolph.

A clean solution without triggers: add redundant columns and include them in FOREIGN KEY constraints, which are the first choice to enforce referential integrity. Related answer on dba.SE with detailed instructions:

• Enforcing constraints “two tables away”

Another option would be to "fake" an IMMUTABLE function doing the check and use that in a CHECK constraint. Postgres will allow this, but be aware of possible caveats. Best make that a NOT VALID constraint. See:

• Disable all constraints and table checks while restoring a dump