It sounds like a nasty case of spyware - best all-purpose tool for that it
Spybot Search and Destroy. It's free, so that won't be a problem.
If you're running Norton Antivirus, that will take care of it as well. Info from the Symantec Anti-virus Research Center on this trojan
here.
Also, it looks like there's a whole lot of things like this. Googling for "RoyalSearch removal" turned up
this page. RoyalSearch isn't mentioned explicitly, but it's in the keywords at the bottom of the page. There's a removal tool there, see if it helps.
Long term, though, it would help to use another browser. (I'm assuming you use Internet Explorer.)
Mozilla, particularly the stripped-down version
Mozilla Firebird is a great substitute.