Never follow links in unexpected emails. It's a common scam to tell people they've purchased something to panic them into revealing their ID and password. You should change both, and if you haven't set up two-factor authentication you should do so to provide an extra level of security.
Changing your Apple ID
If your primary address (the ID) is an @icloud.com, @me.com or @mac.com address you cannot change it. If it is a non-Apple address you can change it as follows:
- Firstly, sign out of iCloud on all your devices: go to each of your devices and sign out in System Preferences (or Settings)>iCloud - 'Sign out' on a Mac, 'Delete this account' on an iOS device (this will not delete the account from the server). If you have 'Find My iPhone' etc enabled you will need to disable it first. Your synced data will disappear from your devices but will reappear when you sign back in.
- Create a new email address, for example at Yahoo or Gmail, or anywhere convenient (or you can use an existing address as long as it is not associated with an Apple ID). You can change it to another Apple address only if it's listed when you click the link to change (in practice this means your main @icloud.com address, and the equivalent @me.com and @mac.com versions if you have them: it does not include email aliases).
- Go to http://appleid.apple.com and click 'Manage your Apple ID'. Sign in with the current ID.
- Where it says 'Apple ID' and gives your current ID email address, click 'Change your Apple ID'.
- Enter your new address and click 'Save changes'
- Sign back into iCloud on all your devices with the new ID and password. Your synced data will reappear (give it time).
I reiterate - before you start, sign out of iCloud on all your devices. Failure to do this will lead you into difficulties.
Changing Apple ID password
1. Before doing anything, turn off 'Find my iPhone/iPad/Mac' on any devices it's enabled on.
2. Sign out of iCloud on all your devices. On a Mac, System Preferences>iCloud and click 'Sign out'. On an iOS device, Settings>iCloud and click 'Delete account' (this will not delete the account from the server) or Sign out' as applicable. Your iCloud-synced data will disappear from your device. If offered the opportunity to save it on your Mac, don't.
3. Go to https://appleid.apple.com, sign in and click 'Password & Security' in the sidebar. Answer the security questions, if set, and then click 'Edit' next to the password field. Save.
4. Sign back in on all your devices. Your data will re-appear (give it time). You can now re-enable 'Find My...'.
I reiterate, before you start, turn off 'Find My...'or you will need the services of Support.