I did this when I had to switch hosts from awful, unreliable Fuitadnet. They managed the domain for me so I emailed them that I wanted to transfer my domain. (I transferred to GoDaddy.)
I don't remember all of the details, but I seem to recall it was a multiple-handshake process. First, they had to get my current registrar to release the domain; this involved having an email sent to me so I could confirm I actually wanted to release the domain. Then, I got a confirmation code that I sent to the new registrar, who did something or the other and came back with a new confirmation code. Once I entered the final confirmation code, the domain belonged to the new registrar. It took a few days and for some reason my first set of codes didn't work, but I found GoDaddy was pretty good at explaining what was going on.
I did have to pay a transfer fee, but the registration retained its length. I opted to renew it because there was a discount at the time.
If you contact your current host/registrar and they should be able to help you out; this was one of the few times I actually got good service out of fuitadnet.