Mysql (Ver 14.14/Redhat): is a new column with default values efficient on column creation?
You're using mysql 5.1,  This means the only engines you'll have available are MyISAM or innodb. in both cases adding a new column, regardless of nullability will require a complete, blocking, table rebuild during alter table.

You maybe be able to use the pt-online-schema change tool that does some tricks to rebuild the table in a less blocking manner but may not work out if you have complicated composite primary keys.

If you have a more recent version (5.6.22 Percona Build) you could use a tokudb storage engine that allows you to to "instantly" add columns.  The way it's indexing works it propagates changes down as they're accessed.