Mathematica notebooks are, of course, plaintext files -- it seems reasonable to expect that they should play nice with a version-control system (git in my case, although I doubt the specific system matters). But the fact is that any .nb file is full of cache information, timestamps, and other assorted metadata. Scads of it.
Which means that limited version control is possible -- commits and rollbacks work fine. Merging, though, is a disaster. Mathematica won't open a file with merge markers in it, and a text editor is no way to go through a .nb file.
Has anyone had any luck putting a notebook under version control? How?
It's recommended to disable the file outline cache, which is the metadata you're referring to when you look at the notebook with a text editor. As you discovered, it can cause merge conflicts if multiple parties are editing the same notebook.
This is easily disabled with the Option Inspector. In the Mathematica menu, go to Format → Option Inspector..., in the top-left set the scope dropdown to Selected Notebook and search for FileOutlineCache in the search field. Set the option to False and save your notebook, and you should be all set.
Note that this can make opening notebooks a little slower, but unless the notebook is rather large, you probably won't notice the difference.