Here is a step by step summary of what I did to get to get Redmine up and running on Debian 5.x (Linux etch55 2.6.24-24-openvz #1 SMP Fri Sep 18 19:57:34 UTC 2009 i686 GNU/Linux)
If you don't know what Redmine is, it is like Trac, but better and on Rails. If you don't know what Trac is you probably wouldn't be interested in Redmine, so you can stop reading.
What it took?
2. Install the necessary Debian packages. This is what I had to do on an OpenVZ VE, so you your packages may differ slightly: ruby ruby-dev irb sqlite3 ri libzlib-ruby libsqlite3-ruby libmysql-ruby mysql-serer mysql-client libopenssl-ruby
3. Install Rubygems the normal way. I installed 1.3.5. I created a symlink for gem1.8 just because.
4. Read the Redmine Installation Guide. Most of what you need to know is there, and I'm not going to repeat what it is there because it should just work, especially if you are familiar with rails or the configuration of rails apps.
5. Install rails and rake. I installed rails 2.1.2 based on the minimum for the 0.8x of redmine. I assume more recent versions of rails will work.
6. Download the stable release of Redmine.
7. You should have already configured mysql-server during the install, but make sure you put your password in the database.yml.
8. Create your database.yml, the session key and run the various rake scripts in the installation guide.
9. Fire up with webrick and login with admin/admin.
What went Wrong?
The main issues I had were related to not installing the right Debian packages. For example you definitely need libopenssl-ruby or the startup scripts will fail. I also screwed up the database.yml.
What Next?
Get git working following the instructions here. But first I need to work on my git skills, since I mostly have used subversion.