It actually doesn't accept NULL values it considers it as empty string. That's because you have your server in non-strict mode. That controls how MySQL handles invalid or missing values in inserts and updates. You can read more about modes here: http://dev.mysql.com/doc/refman/5.6/en/sql-mode.html#sql-mode-strict

mysql> insert into cities(state_id) values (20);
Query OK, 1 row affected, 1 warning (0.07 sec)

mysql> show warnings;
+---------+------+-------------------------------------------+
| Level   | Code | Message                                   |
+---------+------+-------------------------------------------+
| Warning | 1364 | Field 'name' doesn't have a default value |
+---------+------+-------------------------------------------+

mysql> select name is null from cities where id = LAST_INSERT_ID();
+--------------+
| name is null |
+--------------+
|            0 |
+--------------+
1 row in set (0.00 sec)

mysql> SET sql_mode = 'STRICT_ALL_TABLES';
Query OK, 0 rows affected (0.00 sec)

mysql> insert into cities(state_id) values (20);
ERROR 1364 (HY000): Field 'name' doesn't have a default value

You should use IS NOT NULL. (The comparison operators = and <> both give UNKNOWN with NULL on either side of the expression.)

SELECT * 
FROM table 
WHERE YourColumn IS NOT NULL;

Just for completeness I'll mention that in MySQL you can also negate the null safe equality operator but this is not standard SQL.

SELECT *
FROM table 
WHERE NOT (YourColumn <=> NULL);

Edited to reflect comments. It sounds like your table may not be in first normal form in which case changing the structure may make your task easier. A couple of other ways of doing it though...

SELECT val1 AS val
FROM  your_table
WHERE val1 IS NOT NULL
UNION ALL
SELECT val2 
FROM  your_table
WHERE val2 IS NOT NULL
/*And so on for all your columns*/

The disadvantage of the above is that it scans the table multiple times once for each column. That may possibly be avoided by the below but I haven't tested this in MySQL.

SELECT CASE idx
         WHEN 1 THEN val1
         WHEN 2 THEN val2
       END AS val
FROM   your_table
        /*CROSS JOIN*/
       JOIN (SELECT 1 AS idx
                   UNION ALL
                   SELECT 2) t
HAVING val IS NOT NULL  /*Can reference alias in Having in MySQL*/

In MySQL, each column type has an "implicit default" value.

For string types [the implicit] default value is the empty string.

If a NOT NULL column is added to a table, and no explicit DEFAULT is specified, the implicit default value is used to populate the new column data¹. Similar rules apply when the DEFAULT value is specified.

As such, the original DDL produces the same results as:

-- After this, data will be the same, but schema has an EXPLICIT DEFAULT
ALTER TABLE t ADD c varchar(10) NOT NULL DEFAULT ''
-- Now we're back to the IMPLICIT DEFAULT (MySQL stores NULL internally)
ALTER TABLE t ALTER c DROP DEFAULT

The "strict" mode settings affects DML statements relying on default values, but do not affect the implicit default usage when the column is added.

For data entry into a NOT NULL column that has no explicit DEFAULT clause, if an INSERT or REPLACE statement includes no value for the column [and if] strict SQL mode is enabled, an error occurs ..

Here is an sqlfiddle "proof" that strict mode does not apply to the ALTER TABLE .. ADD statement.

¹ This is a MySQL feature. Other engines, like SQL Server, require an explicit DEFAULT (or NULL column) constraint for such schema changes.

Just use an ALTER TABLE... MODIFY... query and add NOT NULL into your existing column definition. For example:

ALTER TABLE Person MODIFY P_Id INT(11) NOT NULL;

A word of caution: you need to specify the full column definition again when using a MODIFY query. If your column has, for example, a DEFAULT value, or a column comment, you need to specify it in the MODIFY statement along with the data type and the NOT NULL, or it will be lost. The safest practice to guard against such mishaps is to copy the column definition from the output of a SHOW CREATE TABLE YourTable query, modify it to include the NOT NULL constraint, and paste it into your ALTER TABLE... MODIFY... query.

NULL means you do not have to provide a value for the field...

NOT NULL means you must provide a value for the fields.

For example, if you are building a table of registered users for a system, you might want to make sure the user-id is always populated with a value (i.e. NOT NULL), but the optional spouses name field, can be left empty (NULL)

From the MySQL documentation (emphasis mine):

Declare columns to be NOT NULL if possible. It makes SQL operations faster, by enabling better use of indexes and eliminating overhead for testing whether each value is NULL. You also save some storage space, one bit per column. If you really need NULL values in your tables, use them. Just avoid the default setting that allows NULL values in every column.

So, on the contrary, NOT NULL saves disk space, rather than costing more.