I don't know anything about it, so I have to ask ...
I have a domain name registered with dotster: MyOld.com Maybe I will get a new domain name: MyNew.com
The search engine rating is quite high, so I don't want to loose MyOld.com. Right now it is pointing to my old shared webhost. But I found a new webhost. What do I have to do?
This depends on your webhost. Many have a DNS service that will set the authoritative web servers for you. Otherwise you can just set the CNAME on the domain to that of your new webhost.
Changing the underlying host should have no discernable impact on your search engine rank,etc.
Yes! Absolutely.