I am not sure why I have never pusued this until today, but I for some reason have never spent the time to figure out why I didn't have spell checking in my Evolution mail client. I knew that Evolution used the packages aspell and gnome-spell, which I already had installed, so why wasn't it working?

When I went into my composer settings in the Evolution preferences, I saw a big empty box that was the list of dictionaries that Evolution was using.  You would think there would be some method of adding them from there, but unfortunately it isn't quite that obvious. To add the English dictionary I had to install the package aspell-en. Once I added this I reopened Evolution and Bamn!

There it is. For the copy/paste inclined, try the following:

#sudo apt-get install aspell gnome-spell aspell-en