It's not nearly has hard when you know what the hell you're doing.  Oh by the way, that's not the case with me <_<  Find an installation guide elsewhere (or even adapt the actual installation guide from Redmine).  This guide is manually how to setup rewrite rules properly so you can use Redmine as ether a proper subdomain entry (redmine.yourdomain.com) or even slightly more tricky, as a subdomain entry (www.yourdomain.com/redmine).  Sadly cPanel htaccess rules generated from their interface ... suck.  Pretty badly >_>  No idea why.

MOVING ON.

Bit 1
Go into cPanel -> Ruby on Rails
Create a new application by entering the application name.  Be happy with the default location it will store your application (/rails_apps/redmine for example)
Ensure it's going to start when someone reboots the server on you (sif they'd do that anyway).  Tick "Load on Boot".
Don't bother starting the application yet.
Find out which port you've been assigned - click "URL" and you should be taken to a page that can not be displayed - you'll see something like http://yourdomain:PORTNUMBER - the portnumber folks is important.

Bit 2
Go into cPanel -> MySQL databases
Generate a new database, a new username/password and ensure you assign the new user to the database we just created.

Bit 3
Get into shell or FTP (whatever is available to you) and remove everything that's pre-generated under ~/rails_apps/redmine
Extract the latest redmine application source and put it in that folder we just cleaned out.
Copy config/database.yml.example to config/database.yml
Edit that file, change the stuff about production and what your MySQL details are (seek the real installation for more info - http://www.redmine.org/wiki/redmine/RedmineInstall)Also following that installation guide, ensure you do the following parts
Get into shell as your cpanel user and enter the following funky stuffs; 

cd ~/rails_app/redmine
RAILS_ENV=production rake config/initializers/session_store.rb
RAILS_ENV=production rake redmine:load_default_data

Bit 4
In cPanel -> Ruby Applications, you can go ahead and start the server now.

Now here comes the main part of this little installation guide (there are more completed installation guides out there on the web guys.

THE IMPORTANT HTACCESS REWRITE BIT

Wherever your "public" html access is, go there and create a .htaccess file.  For example if redmine is being put in your main domain's location, your location will be ~/public_html/.htacces - if it's a subdomain it's typically ~/public_html/subdomain/.htaccess unless you specified otherwise (which I always recomment... shoving subdomains under another domains document root is tacky, especially when dealing with .htaccess)

For "Whole" domain/subdomain (http://redmine.yourdomain.com) installations, put in the following text in the htaccess file

RewriteEngine on
RewriteCond %{HTTP_HOST} ^redmine.yourdomain.com$ [OR]
RewriteCond %{HTTP_HOST} ^www.redmine.yourdomain.com$
RewriteRule ^.*$ "http\:\/\/127\.0\.0\.1\:12001%{REQUEST_URI}" [P,QSA,L]

The two RewriteCond(itions) there are limiting this to the subdomain redmine.  If you aren't playing with a subdomain you can actually remove those two lines. This htaccess example is "pretty much" what cPanel generates at time of writing, minus the "^.*$" part, for whatever reason they're still having ? inserted in there which naturally, causes headaches.

Now the uber tricky part.  You want it to be http://www.yourdomain.com/redmine - a "directory".
First up - edit ~/rails_apps/redmine/config/environment.rb and at the very end of the file (even after the "end" part) add the following

Redmine::Utils::relative_url_root = "/redmine"

In your htaccess file, you'll want to do the following.

RewriteEngine On
RewriteRule ^redmine$ http://localhost:12002/$1 [P,QSA,L]
RewriteRule ^redmine/(.*)$ http://localhost:12002/$1 [P,QSA,L]

Again, ignoring the Rewrite conditions if you aren't setting up /redmine on a subdomain.

Notice where the 12001 part is in the htaccess files, you'll want to change that to whatever port number cPanel has set your redmine application to.

Edit: Updated htaccess rule for the subdirectory. It appears that despite my efforts redmine would only work if there was a trailing slash. Without it, it wasn't working. Then I got it working the other way around.... and now... I have two rules... not ideal but it's working again. \o/