Can table columns with a Foreign Key be NULL?

Yes, that will work as you expect it to. Unfortunately, I seem to be having trouble to find an explicit statement of this in the MySQL manual.

Foreign keys mean the value must exist in the other table. NULL refers to the absence of value, so when you set a column to NULL, it wouldn't make sense to try to enforce constraints on that.

I found that when inserting, the null column values had to be specifically declared as NULL, otherwise I would get a constraint violation error (as opposed to an empty string).

Yes, you can enforce the constraint only when the value is not NULL. This can be easily tested with the following example:

CREATE DATABASE t;
USE t;

CREATE TABLE parent (id INT NOT NULL,
                     PRIMARY KEY (id)
) ENGINE=INNODB;

CREATE TABLE child (id INT NULL, 
                    parent_id INT NULL,
                    FOREIGN KEY (parent_id) REFERENCES parent(id)
) ENGINE=INNODB;


INSERT INTO child (id, parent_id) VALUES (1, NULL);
-- Query OK, 1 row affected (0.01 sec)


INSERT INTO child (id, parent_id) VALUES (2, 1);

-- ERROR 1452 (23000): Cannot add or update a child row: a foreign key 
-- constraint fails (`t/child`, CONSTRAINT `child_ibfk_1` FOREIGN KEY
-- (`parent_id`) REFERENCES `parent` (`id`))

The first insert will pass because we insert a NULL in the parent_id. The second insert fails because of the foreign key constraint, since we tried to insert a value that does not exist in the parent table.