I have a domain myxyz.com (+hosting) purchased from and set up in hosting site A.
My magento installation is on hosting site B.
How can I link this domain to the magento-website such that when someone hits my url myxyz.com (which is on site A), it opens up the magento store front (hosted on site B)?
Note: I want the url myxyz.com to redirect to my magento based website (which is also myxyz.com)
Look at the DNS records for your domain and change the IP address to that of the server where your magento installation is.
If you don't know how to do that ask the company hosting your domain to do it for you (get the IP address from the hosts of site B and tell your domain hosts what it is).
It can take up to 24 hours for the changes to propagate round the internet but in reality it usually happens within a coupe of hours these days.
If your hosting on hosting A allows mulitple domains then you just need to update the nameservers for domain myxyz.com to your hosting on which site is hosted i.e site B and after that you need to login to cpanel and add an addon domain . You just need to fill some simple fields and add it.
see http://www.inmotionhosting.com/support/edu/cpanel/cpanel-manage-domains/adding-addon-domains-in-cpanel for detailed reference
contact your server support or check the email from your hosting provided which has name server information
if your hosting does not allows multiple domain then on domain myxyz.com create an index.php file and write the code to redirect to your magento site.
header('Location: your magento domain');
will do the trick but i am not sure how it will affect your SEO. You may also use htaccess to redirect. try http://www.inmotionhosting.com/support/website/redirects/setting-up-a-301-permanent-redirect-via-htaccess for using htaccess redirects
