I have a domain, serviced by a registrar. When I change email providers, I go to the registrar's site and point my email address at my new provider. That might take a little time (way less than a day, by observation) to propagate. I then go to my new provider and set things up to "send mail as me@mydomain." If you run a local client like Thunderbird (rather than run exclusively through your provider's web interface), then you'll need to do similar there (like point it at your provider's smtp and imap/pop3 servers).

Problems arise when you run your own server, because of fairly detailed authentication settings. If you pay a provider to run their servers, they take care of that.