Removing spaces from files is simple:
Rename only replaces the first occurrence, so you may have to run this a bunch of times until all the spaces are gone.
For regular expressions, Ubuntu (and probably others) come with a perl version of rename instead of the one that comes with Fedora. It is attached. Just rename it to prename.pl or something and chmod +x it. To change spaces to underscores, you can then run it like:
$ prename 's/ /_/g' *