Here is a dump of all the commands I typed in to install Redmine onto a blank Ubuntu install.

I am not saying this is the best way to do it (there are definitely better ways to install the dependencies ahead of time) but it worked for me.

sudo apt-get update
sudo apt-get install build-essential
curl -L | bash -s stable --rails
source /usr/local/rvm/scripts/rvm
rvm pkg install zlib
rvm remove 1.9.2
rvm install 1.9.2
rvm use 1.9.2 --default
gem install rails
sudo apt-get install mysql-server mysql-server-5.5 libmysql-ruby libmysqlclient-dev mysql-client-5.5 mysql-common
#Enter MySQL root password twice
gem install mysql2
gem install bundler
mkdir /home/redmine
cd /home/redmine
tar xzvf redmine-2.1.0.tar.gz
rm redmine-2.1.0.tar.gz 
mv redmine-2.1.0/* ./
rm -r redmine-2.1.0/
bundle install --without development test postgresql sqlite rmagick
mysql -uroot -proot_password
create database redmine character set utf8;
create user 'redmine'@'localhost' identified by 'redmine_password';
grant all privileges on redmine.* to 'redmine'@'localhost';
cp config/database.yml.example config/database.yml
vi config/database.yml
#Edit databases to suit your needs
rake generate_secret_token
rvm pkg install openssl
rvm reinstall 1.9.2 --with-openssl-dir=$rvm_path/usr
RAILS_ENV=production rake db:migrate
RAILS_ENV=production rake redmine:load_default_data
#select your language
ruby script/rails server webrick -e production