So, now links work. I had decided to change the permalink mode from the "ugly" default to "almost pretty", which makes permalinks look like http://www.twofishcreative.com/michael/blog/2007/02/27/wordpress-woes/. What I didn't do was create an .htaccess file so that WordPress could use apache's mod_rewrite to make sure that those almost pretty links actually work. All I needed to do was ssh to my host, change to my blog directory and

% touch .htaccess
% chmod 666 .htaccess

Then when I chose the almost pretty permalink option WordPress updated the .htaccess file to include the necessary rewrite rules. More information can be found under the Wordpress permalinks documentation.