git push says “everything up-to-date” even though I have local changes

Are you working with a detached head by any chance?

As in:

indicating that your latest commit is not a branch head.

Warning: the following does a git reset --hard: make sure to use git stash first if you want to save your currently modified files.

$ git log -1
# note the SHA-1 of latest commit
$ git checkout master
# reset your branch head to your previously detached commit
$ git reset --hard <commit-id>

---

As mentioned in the git checkout man page (emphasis mine):

It is sometimes useful to be able to checkout a commit that is not at the tip of one of your branches.
The most obvious example is to check out the commit at a tagged official release point, like this:

$ git checkout v2.6.18

Earlier versions of git did not allow this and asked you to create a temporary branch using the -b option, but starting from version 1.5.0, the above command detaches your HEAD from the current branch and directly points at the commit named by the tag (v2.6.18 in the example above).

You can use all git commands while in this state.
You can use git reset --hard $othercommit to further move around, for example.
You can make changes and create a new commit on top of a detached HEAD.
You can even create a merge by using git merge $othercommit.

The state you are in while your HEAD is detached is not recorded by any branch (which is natural — you are not on any branch).
What this means is that you can discard your temporary commits and merges by switching back to an existing branch (e.g. git checkout master), and a later git prune or git gc would garbage-collect them.
If you did this by mistake, you can ask the reflog for HEAD where you were, e.g.

$ git log -g -2 HEAD