I have a domain name (let's call it myfirst.com) hosted by one of the
providers. I also have another domain name (let's call it
mysecond.com). The second domain is not hosted by anyone at all and I
want the e-mail that goes into second domain to be automatically
re-directed to the first domain (so that user@mysecond.com ->
user@myfirst.com). I modified the MX record for mysecond.com to point
to myfirst.com. Now I'm getting the mail sent to mysecond.com bounced
back by myfirst.com with "relay attempt failed". What else should I do
to enable the re-direction. Myfirst.com is hosted on a shared Linux
box (I don't have root privileges).

You want to amend the hostnames for which myfirst.com will accept mail.
How you do this depends on the MTA in use but will require root.

Currently it looks as if the mail for mysecond is getting redirected to myfirst 
(partial success) but then myfist thinks "This is not for me - and
it's not my job to pass it on" - hence the message about relaying.

Thanks, bozo99-ga.

I will accept as an answer a how-to instruction (make believe that I
have root). The system is running ESMTP Sendmail 8.11.6p2/8.11.6 on
Linux 2.4.

Try adding mysecond.com to the file /etc/mail/local-host-names (on a
separate line) and restarting sendmail.

You will need root to do this.

You are going to need to know what mailer is being used on the
firstdomain.com. There are quite a few out there. Qmail, Exim,
Sendmail, etc. This list goes on and one. Once the mailer is
determined on myfirst.com's MX, you will need add mysecond.com as a
list of accepted local domains on the myfirst.com MX.

To do this in qmail, you would add mysecond.com to the file
/var/qmail/control/locals (or similar, could be /var/qmail/locals, or
whereever qmail was installed)

To do this in exim, you would add mysecond.com to the line beginning
with local_domains in /etc/exim/exim.conf (or similar, could be
/etc/exim.conf, or whereever exim was installed)

To do this in sendmail, you would want to add mysecond.com to a line
beginning with Cw (this means local domain) in /etc/sendmail.cf or
whereever the sendmail configuration file resides.

After adding the local domain to whatever mailer process, the process
MAY have to be restarted or signalled (kill -HUP process_id) to reread
it's configuration files.