How do I clean up my Github fork so I can make clean pull requests?

Step 1: Pull upstream changes
It's recommended to add the upstream repo as "upstream" as explained on the Fork a Repo page:

git pull --rebase upstream master

The --rebase option places your changes on top of the latest commit without merges.

Step 2: (Optional) Merge your commits into 1 commit

git reset --soft upstream/master

This command will "undo" all your commits, but won't change the files. So you can commit all your changes in a single commit.

git commit -a

Step 3: Check & test your changes

To show the changes use a GUI like the built-in gitk, Sourcetree, TortoiseGit or Tower (paid), etc.

Step 4: Push

git push will throw an error, because the push would change the target repository's history.
If you're confident the changes shown in step 3 are correct then push with "-f"

git push -f origin master

Additional information
The command to add a remote is:

git remote add upstream git://github.com/[username]/[project].git

You can also also pull from a direct URL:

git pull --rebase  git://github.com/[username]/[project].git

But then you'll need the hash of the latest upstream commit instead of "upstream/master" in the other steps.

As I understand it, with both Git and Mercurial (I've only used the latter, so I may be wrong) it isn't a big deal at all to blow away a fork and re-fork it. I do that all the time with my projects. If you're ok with doing that (can back up your changes, or don't have any significant changes in your fork), I'd say that's probably the way to go.

Remember, with DVCS, forking a repository makes a full clone of that entire repo. If you delete your current fork and then fork the original repo again, you'll have a completely clean slate to work from.