How do I setup a foreign key relationship based on two columns? I have the following two tables:

CREATE TABLE [dbo].[company]
    (
      [CompanyID] [int] NOT NULL ,
      [CompanyName] [varchar](150) NULL ,
      [DepartmentID] [int] NOT NULL ,
      [DepartmentName] [varchar](150) NULL ,
      [ResidentialAddress] [varchar](500) NULL ,
      [ResidentialSuburb] [varchar](150) NULL ,
      [ResidentialPostCode] [varchar](20) NULL ,
      [ResidentialState] [varchar](150) NULL ,
      [ResidentialCountry] [varchar](100) NULL ,
      [PostalAddress] [varchar](500) NULL ,
      [PostalSuburb] [varchar](150) NULL ,
      [PostalPostCode] [varchar](20) NULL ,
      [PostalState] [varchar](150) NULL ,
      [PostalCountry] [varchar](100) NULL ,
      [Phone] [varchar](50) NULL ,
      [IsActive] [bit] NOT NULL ,
      [Created] [datetime] NULL ,
      [CreatedBy] [varchar](50) NULL ,
      [LastModified] [datetime] NULL ,
      [LastModifiedBy] [varchar](50) NULL ,
      CONSTRAINT [PK_department] PRIMARY KEY CLUSTERED ( [DepartmentID] ASC )
        WITH ( PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
               IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON,
               ALLOW_PAGE_LOCKS = ON ) ON [PRIMARY]
    )
ON  [PRIMARY]


AND

CREATE TABLE [dbo].[user]
    (
      [UserId] [int] NOT NULL ,
      [CompanyID] [int] NOT NULL ,
      [DepartmentID] [int] NOT NULL ,
      [EmailAddress] [varchar](150) NOT NULL ,
      [Title] [varchar](50) NULL ,
      [FirstName] [varchar](100) NOT NULL ,
      [MiddleName] [varchar](100) NULL ,
      [LastName] [varchar](100) NULL ,
      [DateOfBirth] [date] NULL ,
      [ResidentialAddress] [varchar](500) NULL ,
      [ResidentialSuburb] [varchar](150) NULL ,
      [ResidentialPostCode] [varchar](20) NULL ,
      [ResidentialState] [varchar](150) NULL ,
      [ResidentialCountry] [varchar](100) NULL ,
      [PostalAddress] [varchar](500) NULL ,
      [PostalSuburb] [varchar](150) NULL ,
      [PostalPostCode] [varchar](20) NULL ,
      [PostalState] [varchar](150) NULL ,
      [PostalCountry] [varchar](100) NULL ,
      [Phone] [varchar](50) NULL ,
      [Mobile] [varchar](50) NULL ,
      [BrowserDetails] [varchar](500) NULL ,
      [IsActive] [bit] NOT NULL ,
      [LastLogin] [datetime] NULL ,
      [Created] [datetime] NULL ,
      [CreatedBy] [varchar](50) NULL ,
      [LastModified] [datetime] NULL ,
      [LastModifiedBy] [varchar](50) NULL ,
      CONSTRAINT [PK_users] PRIMARY KEY CLUSTERED ( [UserId] ASC )
        WITH ( PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
               IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON,
               ALLOW_PAGE_LOCKS = ON ) ON [PRIMARY]
    )
ON  [PRIMARY]


I would like a foreign key on dbo.user where a company id and department id identifies the correct row on dbo.company. Is something like this possible?
Yes, by adding a UNIQUE constraint (or a unique index) on the company table, using these 2 columns:

ALTER TABLE company
  ADD CONSTRAINT CompanyID_DepartmentID_UQ
    UNIQUE (CompanyID, DepartmentID) ;


Then you can add the foreign key:

ALTER TABLE [user]
  ADD CONSTRAINT Company_User_FK
    FOREIGN KEY (CompanyID, DepartmentID) 
    REFERENCES company (CompanyID, DepartmentID)  ;


Test at SQL-Fiddle


Minor comment: Since the table company has DepartmentID as the primary key, shouldn't it be called department table? (How do you call the table where the CompanyID is the primary key?)