Did you simply upload the application into your website directory, or are you using symbolic links? Normally with cgi/fcgi, you're better off having the actual application in a non-web accessible directory, and a symlink from your public_html/ (or whatever the web directory is called), which points to the app/public/ directory. However, it could be possible to get it to work without symlinks.
Now, the following information is general/generic and encompasses several popular shared Rails hosts. However, it's certainly possible that your host have different settings. In that case, it would very much help if you could tell us which host you're using.
Inside your app/public/ directory, there should be a file called dispatch.fcgi. First of all, verify that this file is there. If it is, make sure that the file is chmodded to 755 and try changing the first line to:
#!/usr/bin/ruby18
if it is:
#!/usr/bin/ruby
(This may vary depending on your host.)
In your app/public/ directory, there should also be a file called .htaccess. In it, change the following line:
RewriteRule ^(.*)$ /dispatch.cgi?$1 [QSA,L]
to:
RewriteRule ^(.*)$ /dispatch.fcgi?$1 [QSA,L]
If neither of these changes work, please post the full contents of dispatch.fcgi, .htaccess and explain the directory structure of your hosting account. As previously stated, letting us know which host you're using would definitely be helpful too.