1. Go to account.mojang.com
2. Sign in to your Mojang account by clicking right next to the Mojang logo on the button where it says "Log In", then enter your email and password.
3. Under the "My Games" heading, you should see the subheadings: "Game, Since, Profile Name, Download Game"
4. Under "Profile Name", you should see your username in hypertext next to "(Change)" in parentheses.

It should look like this: SkyDoesMinecraft (Change)

5. Click on "(Change)" and you should be redirected to a page under which the heading says: "Rename Profile"
6. From there, enter in your desired new profile name under "New profile name:" in the box that says in very faint text: "Enter Desired Name" and click on the box next to it that says "Check availability".
7. If the name is available, you will have to enter your password down below under the heading that says "Password" and click the button that says "Change Name". If the name is not available, you will have to either be content with your existing name or come up with another.

CAUTION: you have to wait 30 days before you can change your name again, so choose wisely!

Update

There may have been changes to how you change your data on Minecraft's servers.

Changes to the following are made on https://minecraft.net/en-us/profile:

• Username changes—rate limited to 30 days per change
• Password changes

Changes to the following are made on https://account.mojang.com/me/settings:

• Email changes—indirect, email will be sent with instructions
• Changes to your security questions—indirect, email will be sent with instructions
• Account deletion

Changes to the account's registration birthdate should not be made unless the account is being given to a new user. Customer Service must be contacted to make the change.