Set up new mailboxes and aliases: You'll need one mailbox on your new IMAP server for each user you're moving. If you used a custom domain, you'll want the new email accounts to be exactly the same as the old ones. If you had set up any aliases (that is, extra addresses that point to a single account) in Gmail, configure those for the new provider, too.
Forward your Gmail: If you did not use a custom domain--meaning that your address ended in @gmail.com or @googlemail.com--log in to your Gmail account on the Web (just as before), click the gear icon, and choose Settings from the pop-up menu. Click Forwarding and POP/IMAP, and then click Add a Forwarding Address. Type the address of your new account, and follow the prompts to confirm it. By performing this step, you'll ensure that email sent to your Gmail address will still reach you.
Add the new account in Mail: In Mail, choose Mail > Preferences, click Accounts, and click the plus (+) button. Select Add Other Mail Account and follow the instructions to add an IMAP account with the username, password, and server addresses of your new provider. After you enter your credentials, Mail will attempt to automatically configure the account; if automatic configuration fails (which is likely), Mail will prompt you to enter the necessary details manually.
At this point, you have both your old Gmail account and your new IMAP account set up in Mail. Incoming messages will start flowing into the new account shortly, but you'll still be able to access your Gmail account. That's important, because it enables you to perform the next step.
Move your mailboxes and messages: Choose Mailbox > New Mailbox and create a mailbox (any name will do) in your new IMAP account. Doing this forces that account name to appear in Mail's sidebar. Now you can drag a mailbox from your Gmail account in the sidebar to the new IMAP account label to copy it to the new location.
In some cases, this move copies only the mailbox and not its contents; you may have to go back to the Gmail mailbox, select everything inside it, drag it to the corresponding mailbox on the new IMAP server, and repeat as needed. (I recommend choosing Window > Activity to keep an eye on the progress; it can take a longtime.)
Once you've confirmed that all your messages and mailboxes have moved from Gmail to the new account, you can remove the Gmail account from Mail. In Mavericks, you must select the account in the Internet Accounts pane of System Preferences and click the minus (-) button.
Odds and ends
Sign up for CIO Asia eNewsletters.