We've got a fresh CentOS box and we need to enable nice urls / permalinks. We're running Apache with mod_rewrite installed but I'm aware I need edit a few config files to get the basics up and running.
What are the steps and files that need to be changed in order to get it up and running?
I agree with David Pashley - this is a somewhat vague question.
However I'm going to take a guess from looking at the question tags that you're using Apache as your webserver. In which case you will want to explore Mod_Rewrite http://httpd.apache.org/docs/2.0/mod/mod_rewrite.html and modify either your Httpd.conf or .htaccess files to manipulate url rewrites.
If you're using Lighttpd you would want to look at http://redmine.lighttpd.net/wiki/lighttpd/Docs:ModRewrite
There are still a lot of 'ifs' in your question you might want to elaborate on. Some web frameworks will handle this for you (Rails, Django, CakePHP, etc.)
Just incase anyone else is looking for the answer simply edit
/etc/httpd/conf/httpd.conf
Find the line
Change AllowOverride None to AllowOverride All
Restart, Win