Q:

What exactly is a foreign key?

Ok. So I know what a primary key in  DB is. If you have a table in a database, a primary key is a single value that is unique to each row in your table. For example:
id   | name    | whatever
-------------------------
1      Alice     ....
2      Bob       ....
45     Eve       ....
988    ....      ....

So I need a good, simple example to explain what exactly a foreign key is. Because I just don't get it :)

Edit: OK it's pretty easy, I guess I was over-complicating the problem.
So one final question, the only restriction on foreign keys is that it they are a valid primary key value in the table I am referring to?

A:

A foreign key is a field that points to a primary key of another table.
Example:
Table Name - Users

UserID    UserName    UserRoleID
1         JohnD       1
2         CourtneyC   1
3         Benjamin    2

Table Name - UserRoles

UserRoleID    Desc
1             Admin
2             Moderator

You can see that Users.UserRoleID is a foreign key which points to the primary key UserRoles.UserRoleID
The use of foreign keys makes setting up relationships on other tables simple, allowing you to link together the data of multiple tables in a nice way:
Example:
SELECT
    a.UserID, 
    a.UserName, 
    b.Desc as [UserRole]
FROM 
    Users a INNER JOIN 
        UserRoles b ON a.UserRoleID = b.UserRoleID

Output would then be:
UserID    UserName    User Role
1         JohnD       Admin
2         CourneyC    Admin
3         Benjamin    Moderator

A:

Let's say you have another field, which is the home city:
id   | name    | city
-------------------------
1      Alice     San Francisco
2      Bob       New York
45     Eve       New York
988    Bill      San Francisco

Now, it does not make sense to repeat the same cities in many rows. This could lead you to typos, excessive space usage, difficulties to bring up results among other problems. So you use a foreign key:
id   | name    | fk_city
-------------------------
1      Alice     1
2      Bob       2
45     Eve       2
988    Bill      1

home city table:
id   | name
-------------------------
1    | San Francisco
2    | New York

Hope it makes things clearer for you. :-)
Update: about your final question: Yes. :-)

A:

A foreign key is a column in one table that should uniquely identify something in another table. Thus, the values should correspond to primary keys in that other table.
For example, if you have a table of students taking courses, every record would include a student id and a course id. These are foreign keys into a student table (where there is one record for each student id), and a courses table (where there is one record for each course id).
Referential integrity means that all your foreign keys actually correspond to primary keys in these target tables. For example, all the student ids and course ids in your registration table correspond to real student ids and course ids. 

